#include <cstdio>
#include <vector>
#include <utility>
#define INF 99999999
#define Nmax 50001

using namespace std;
FILE *f1,*f2;
int n,m,i,u,v,c,d[Nmax],x,min1,nod,h[Nmax],pos[Nmax];
vector <pair <int,int> > a[Nmax];

void swap(int i,int j)
{int aux;
aux=h[i];h[i]=h[j];h[j]=aux;
pos[h[i]]=i;pos[h[j]]=j;
}

void push(int x)
{while (x/2 && d[h[x]]<d[h[x/2]])
{swap(x,x/2);
x=x/2;
}
}


void pop(int x)
{int y=0;
while (x!=y)
{y=x;
if (y*2<=m && d[h[x]]>d[h[y*2]]) x=2*y;
if (y*2+1<=m && d[h[x]]>d[h[y*2+1]]) x=2*y+1;
swap(x,y);
}
}

int extract()
{int v=h[1];
h[1]=h[m--];
pop(1);
return v;
}


int main()
{f1 = fopen("dijkstra.in","r");
f2 = fopen("dijkstra.out","w");
fscanf(f1,"%d%d",&n,&m);
for (i=1;i<=m;i++) {fscanf(f1,"%d%d%d",&u,&v,&c);a[u].push_back(make_pair(v,c));}
for (i=1;i<=n;i++) {d[i]=INF;h[i]=i;pos[i]=i;}
d[1]=0;m=n;
while (m)
{nod=extract();
for (i=0;i<a[nod].size();i++)
if (d[a[nod][i].first]>d[nod]+a[nod][i].second)
{d[a[nod][i].first]=d[nod]+a[nod][i].second;
push(pos[a[nod][i].first]);
}
}
for (i=2;i<=n;i++) if (d[i]==INF) fprintf(f2,"0 ");else fprintf(f2,"%d ",d[i]);
fclose(f1);fclose(f2);
    return 0;
}

//Challenges are what make life interesting and overcoming them is what makes life meaningful.