#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

#define N 50000
#define pinf 5000000005
using namespace std;

/*bool operator > (int x, int y)
{
    return D[x]>D[y]; // ordine crscatoare
}*/
priority_queue< int, vector<int>, greater<int> > coada;

long long D[N];
short int n,m,T[N];
//bool S[N];
vector< pair<short int,short int> > L[N];

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

void dijkstra(int r)
{
    int i,poz;
    //double min;
    for(i=1;i<=n;i++)
    {
      D[i]=pinf;
      T[i]=0;
    }
    D[r]=0; T[r]=0;
    coada.push(r);

    while(!coada.empty())
    { //cout<<1;
        poz=coada.top();coada.pop();
        //S[poz]=1;

        for(i=0;i<L[poz].size();i++)
        {
            if(D[L[poz][i].first]>D[poz]+L[poz][i].second )
            {
                D[L[poz][i].first]=D[poz]+L[poz][i].second;
                T[L[poz][i].first]=poz;
              //  if(!S[L[poz][i].first])
                    coada.push(L[poz][i].first);
            }
        }
    }

}

int main()
{
   int x,y,c,i,j;
   f>>n>>m;
  // for(i=1;i<=n;i++)
   //  for(j=1;j<=n;j++)
      //   L[i][j]=pinf;

   for(i=1;i<=m;i++)
   {
      f>>x>>y>>c;
      L[x].push_back(make_pair(y,c));
   }
   dijkstra(1);
   for(i=2;i<=n;i++)
     if(D[i]!=pinf) g<<D[i]<<" ";
     else g<<0<<" ";
   f.close();
   g.close();
   return 0;
}