const infi=maxlongint div 4;
var x,heap,poz,ind,lis:array[0..50001] of longint;
ct,t:array[0..250001] of longint;
n,i,j,k,l,m:longint;

procedure citire;
var y,z,c:array[0..250001] of longint;
begin
assign(input,'dijkstra.in');
assign(output,'dijkstra.out');
reset(input);
rewrite(output);
readln(n,m);
for I:=1 to m do
        begin
        read(y[i],z[i],c[i]);
        ind[y[i]]:=ind[y[i]]+1;
        end;
for i:=2 to n do
        ind[i]:=ind[i]+ind[i-1];
for i:=1 to m do
        begin
        t[ind[y[i]]]:=z[i];
        ct[ind[y[i]]]:=c[i];
        dec(ind[y[i]]);
        end;
end;


begin
for i:=1 to n do x[i]:=infi;
for i:=ind[1]+1 to ind[2] do
        x[t[i]]:=ct[i];
for i:=1 to n do
        begin
        heap[i]:=x[i];
        poz[i]:=i;
        lis[i]:=i;
        if I>1 then upheap(I);
        end;
while N>1 do
begin
aux:=heap[1];