#include <stdio.h>
#include <vector>
using namespace std;
struct hp {long val,gf;} key,aux;
vector <hp> S;
long sol[50001],pos[50001];
vector <hp> V[50001];
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[k].gf]=pos[S[father(k)].gf];
             k=father(k);
                    }
S[k]=key;
pos[S[k].gf]=ps;
}

void down(long n , long k)
{
    int 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) {
            swap(S[k],S[son]);
            swap(pos[S[k].gf],pos[S[son].gf]);
            k=son;
            }

        }
while (son);
}

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

void cut (long &n, long k)
{
pos[S[n].gf]=pos[S[k].gf];
pos[S[k].gf]=-1;

S[k]=S[n--];
S.pop_back();
if (k>1 && S[k].val<S[father(k)].val)
                up(n,k);
          else
                down(n,k);

}

int main() {
f=fopen("grader_test2.in","r");
g=fopen("dijkstra.out","w");
fscanf(f,"%ld%ld",&n,&m);
S.push_back(aux);
long x,y,z;
for (i=1;i<=n;i++) {
                    aux.gf=i;
                    aux.val=inf;
                    S.push_back(aux);
                    pos[i]=i;
                    }
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);
                    }
build(n);
long minp,nn=n,j;
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 (pos[V[minp][j].gf]!=-1 && 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,1);
}
for (i=2;i<=nn;i++) if (sol[i]!=inf) fprintf(g,"%ld ",sol[i]);
                                else fprintf(g,"0 ");
fclose(g);
return 0;
}