#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>

const int NMAX=50001,INF=2147483647;

std::vector<std::pair<int,int> > vecini[NMAX];

std::queue<int> coada;

int val[NMAX];
bool fol[NMAX];

void Init(int n)
{
 for(int i=1;i<=n;i++)
     val[i]=INF;
}

void Bellman_Ford(int n,int m)
{
 coada.push(1);
 val[1]=0;
 int pas=0;
 while(!coada.empty() && pas<=n*m)
       {
        pas++;
        int x=coada.front();
        coada.pop();
        fol[x]=false;
        for(std::vector<std::pair<int,int> >::iterator i=vecini[x].begin();i!=vecini[x].end();i++)
            {
             int a,b;
             a=i->first; b=i->second;
             if(val[x]+i->second<val[i->first])
                {
                 val[i->first]=val[x]+i->second;
                 if(!fol[i->first])
                    {
                     coada.push(i->first);
                     fol[i->first]=true;
                    }
                }
            }
       }
}

int main()
{
 FILE *in=fopen("bellmanford.in","r");
 int n,m;
 fscanf(in,"%d %d ",&n,&m);
 for(int i=1;i<=m;i++)
     {
      int x,y,cost;
      fscanf(in,"%d %d %d ",&x,&y,&cost);
      vecini[x].push_back(std::make_pair(y,cost));
     }
 fclose(in);
 Init(n);
 Bellman_Ford(n,m);
 FILE *out=fopen("bellmanford.out","w");
 for(int i=2;i<=n;i++)
     {
      fprintf(out,"%d ",val[i]);
     }
 fclose(out);
 return 0;
}