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

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

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;
d[1]=0;
while (1)
{min1=INF;
for (i=1;i<=n;i++)
if (!use[i] && d[i]<min1) {min1=d[i];nod=i;}
if (min1==INF) break;
use[nod]=1;
for (i=0;i<a[nod].size();i++)
if (d[nod]+a[nod][i].second<d[a[nod][i].first]) d[a[nod][i].first]=d[nod]+a[nod][i].second;
}
for (i=2;i<=n;i++) if (d[i]!=INF) fprintf(f2,"%d ",d[i]); else fprintf(f2,"0 ");
    return 0;
}

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