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

#define N 50000
#define pinf 5000000005
using namespace std;
long long D[N];

class Compar
{
 public:
 bool operator()(int x, int y)
 {
    return D[x]>D[y]; // ordine crscatoare
 }
};

priority_queue< int, vector<int>, Compar > coada;


int n,m;//,T[N];
//bool S[N];
vector< pair< int, 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]==0)
                    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<<" ";

     //coada.push(10); coada.push(15);coada.push(3);coada.push(16);
    // cout<<coada.top()<<endl; coada.pop();
    // cout<<coada.top()<<endl; coada.pop();
    // cout<<coada.top()<<endl; coada.pop();
    // cout<<coada.top()<<endl; coada.pop();
   f.close();
   g.close();
   return 0;
}