package pass;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Edgex {
int from;
int to;
int weight;
public Edgex(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
class comppq implements Comparator<Edgex>{
@Override
public int compare(Edgex o1, Edgex o2) {
return o2.weight-o1.weight;
}
}
public class Dijkstra {
/*
7 9
0 1 6
1 2 5
0 3 2
3 1 7
3 4 5
4 5 5
4 6 1
1 5 3
5 2 3
*/
static int vs,lines;
static LinkedList<Edgex> Edges = new LinkedList<Edgex>();
static LinkedList<Integer> Visited = new LinkedList<Integer>();
static LinkedList<Integer> VetexsMark = new LinkedList<Integer>();
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
vs=Integer.parseInt(st.nextToken());
lines=Integer.parseInt(st.nextToken());
for(int l=0;l<lines;l++){
st=new StringTokenizer(br.readLine());
int from=Integer.parseInt(st.nextToken());
int to=Integer.parseInt(st.nextToken());
int weight=Integer.parseInt(st.nextToken());
Edgex e=new Edgex(from,to,weight);
Edges.add(e);
}
for(int i=0;i<vs;i++){
VetexsMark.add(Integer.MAX_VALUE/2);
}
runDijkstra(6);
}
public static void runDijkstra(int target){
int start=0;
PriorityQueue<Edgex> pq=new PriorityQueue<Edgex>(new comppq());
pq.add(new Edgex(0,0,0));
VetexsMark.set(0, 0);
Visited.add(start);
while(!pq.isEmpty()){
int current=pq.poll().to;
if(current==target) break;
LinkedList<Edgex> edgexlist=getTargets(current);
for(int i=0;i<edgexlist.size();i++)
{
Edgex cusr=edgexlist.get(i);
if(VetexsMark.get(current)+cusr.weight<VetexsMark.get(cusr.to)){
VetexsMark.set(cusr.to,VetexsMark.get(current)+cusr.weight);
Visited.add(cusr.to);
pq.add(cusr);
}
}
}
for(int k=0;k<VetexsMark.size();k++){
System.out.println("0 --> "+k+" "+VetexsMark.get(k));
}
}
public static LinkedList<Edgex> getTargets(int x){
LinkedList<Edgex> edgexlist=new LinkedList<>();
for(int i=0;i<Edges.size();i++){
if(Edges.get(i).from==x){
edgexlist.add(Edges.get(i));
}
}
return edgexlist;
}
}
