import java.util.*;
class Graph{
Map<Integer,List<Edge>>adjacencyList;
public Graph(){
adjacencyList=new HashMap<>();
}
public void addEdge(int source,int destination,int weight){
adjacencyList.putIfAbsent(source,new ArrayList<>());
adjacencyList.putIfAbsent(destination,new ArrayList<>());
adjacencyList.get(source).add(new Edge(destination,weight));
adjacencyList.get(destination).add(new Edge(source,weight));
}
public Map<Integer,Integer> dij(int start){
PriorityQueue<Edge> pq=new PriorityQueue<>(Comparator.comparingInt(edge->edge.weight));
Map<Integer,Integer> distances=new HashMap<>();
for(Integer node: adjacencyList.keySet()){
distances.put(node,Integer.MAX_VALUE);
}
distances.put(start,0);
pq.add(new Edge(start, 0));
while(!pq.isEmpty()){
Edge curr=pq.poll();
int curnode=curr.node;
int currDist=curr.weight;
for( Edge neighbour:adjacencyList.getOrDefault(curnode, new ArrayList<>()) ){
int newDist=distances.get(curnode)+neighbour.weight;
if (currDist > distances.get(curnode)) {
continue;
}
if(newDist<distances.get(neighbour.node)){
distances.put(neighbour.node, newDist);
pq.add(new Edge(neighbour.node, newDist));
}
}
}
return distances;
}
}
class Edge{
int node;
int weight;
public Edge(int node, int weight) {
this.node = node;
this.weight = weight;
}
}
public class Solution {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int V = s.nextInt();
int E = s.nextInt();
Graph graph=new Graph();
for(int i=0;i<E;i++){
int ei=s.nextInt();
int ej=s.nextInt();
int w=s.nextInt();
graph.addEdge(ei, ej, w);
}
int start=0;
Map<Integer,Integer> ans=graph.dij(start);
for(Map.Entry entry:ans.entrySet()){
System.out.println(entry.getKey()+" "+entry.getValue());
}
}
}