#include <stdio.h>
#include <vector>
using namespace std;
struct hp {long val,gf;} key,aux,S[60001];
long sol[60001],pos[60001];
vector <hp> V[60001];
FILE *f,*g;
long n,m,i;
const long inf=1<<30;
inline long father(long k)
{
 return k/2;
}
inline long lson(long k)
{
    return k*2;
}
inline long rson(long k)
{
    return k*2+1;
}
void up(long n,long k)
{
    key=S[k];
long ps=pos[S[k].gf];

while (k>1 && key.val<S[father(k)].val) {

             S[k]=S[father(k)];
             pos[S[father(k)].gf]=k;
             k=father(k);

                    }
S[k]=key;
pos[S[k].gf]=k;
}

inline void down(long n , long k)
{
    long son;
do {
    son=0;
    if (lson(k)<=n) son=lson(k);
    if (rson(k)<=n && S[rson(k)].val<S[lson(k)].val) son=rson(k);
    if (S[son].val>=S[k].val) son=0;

    if (son) {
            pos[S[k].gf]=son;
            pos[S[son].gf]=k;
            swap(S[k],S[son]);
            //swap(pos[S[k].gf],pos[S[son].gf]);
            k=son;
            }

        }
while (son);
}

inline void build(long n)
{
long i;
    for (i=n/2;i>0;i--)
    down(n,i);
}

inline void cut (long &n)
{
    int con;
pos[S[n].gf]=1;
pos[S[1].gf]=n;

swap(S[1],S[n]);
n--;
down(n,1);

}

int main() {
f=fopen("dijkstra.in","r");
g=fopen("dijkstra.out","w");
fscanf(f,"%ld%ld",&n,&m);
long x,y,z;
for (i=1;i<=n;i++) {
                    aux.gf=i;
                    aux.val=inf;
                    S[i]=aux;
                    pos[i]=i;
                    }
S[1].val=inf+1;
for (i=1;i<=m;i++) {
                    fscanf(f,"%ld%ld%ld",&x,&y,&z);
                    //if (x==1) S[y].val=z;
                    aux.gf=y;  aux.val=z;
                    V[x].push_back(aux);
                    }
//swap(S[1],S[n]);
//swap(pos[1],pos[n]);
S[1].val=0;
build(n);
int con;
long minp,nn=n,j;
//n--;
for (i=1;i<=nn;i++) {
sol[S[1].gf]=S[1].val;
minp=S[1].gf;

for (j=0;j<V[minp].size();j++)
       if ( S[pos[V[minp][j].gf]].val>S[pos[minp]].val+V[minp][j].val) {
                                                             S[pos[V[minp][j].gf]].val=S[pos[minp]].val+V[minp][j].val;
                                                             up(n,pos[V[minp][j].gf]);
                                                                }
cut(n);
if (minp!=pos[S[minp].gf])
con++;
}
for (i=2;i<=nn;i++)  fprintf(g,"%ld ",sol[i]<inf?sol[i]:0);
fprintf(g,"\n");

fclose(g);
return 0;
}