#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");
//FILE *f=fopen("f.in","r");
//FILE *g=fopen("f.out","w");

const long oo=(1<<30);

long N;
long M;
long D[50001];

vector <pair<long ,long> > G[50001];


void Citeste()
{
    fscanf(f,"%ld%ld",&N,&M);
    for(long i=1;i<=M;i++)
    {
        long x,y,dist;
        fscanf(f,"%ld%ld%ld",&x,&y,&dist);
        G[x].push_back(make_pair(y,dist));
    }
}
void Afiseaza()
{
    for(long i=2;i<=N;i++)
    {
       if(D[i]!=oo)
         fprintf(g,"%ld ",D[i]);
       else fprintf(g,"0 ");
    }
}
void Dijkstra(long nodStart)
{
    for(long i=1;i<=N;i++)
        D[i]=oo;
    D[nodStart]=0;
    long c[50001];long p=0,u=0;
    c[0]=nodStart;
    while(p<=u)
    {
        long nodCurent = c[p];

        for(unsigned long i =0;i<G[nodCurent].size();i++)
        {
            long nodVecin = G[nodCurent][i].first;
            long Cost = G[nodCurent][i].second;

            if(D[nodCurent]+Cost<D[nodVecin])
            {
                D[nodVecin]=D[nodCurent]+Cost;
                u++;
                c[u]=nodVecin;
            }
        }
        p++;
    }
}
int main()
{
   Citeste();
   Dijkstra(1);
   Afiseaza();
   fclose(f);
   fclose(g);
   return 0;
}