#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);

bool inCoada[50001];
long N;
long M;
long D[50001];
//long c[50001];
vector <pair<long ,long> > G[50001];


struct compara
{
    bool operator() (int x,int y)
    {
        return D[x]>D[y];
    }
};
priority_queue< int , vector <int>, compara > Coada;


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;
    Coada.push(nodStart);
    inCoada[nodStart]=true;


    while(!Coada.empty())
    {
        long nodCurent =Coada.top();
        Coada.pop();
        inCoada[nodCurent]=false;

        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;
               // if(!inCoada[nodVecin])
                {
                    Coada.push(nodVecin);
                    inCoada[nodVecin]=true;
                }
            }
        }
    }
}
int main()
{
   Citeste();
   Dijkstra(1);
   Afiseaza();
   fclose(f);
   fclose(g);
   return 0;
}