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

#define N 50005
#define pinf 5000030000
using namespace std;

long long D[N];

class Compar  //vezi priority_queue.pdf
{
 public:
 bool operator()( pair<int,int> x, pair<int,int> y)
 {
    return x.second>y.second; // ordine crscatoare
 }
};

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

int n,m;;

vector <vector< pair< int, int> > >L(N);

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

void dijkstra(int r)
{
    int i,poz,c;

    for(i=1;i<=n;i++)
      D[i]=pinf;

    coada.push(make_pair(r,0));D[r]=0;

    while(!coada.empty())
    {

        poz=coada.top().first;  //extragem din coada nodul poz si costul c,
        c=coada.top().second;    //cu care a fost pus poz in coada
        coada.pop();

     //   if(D[poz]==c)  //daca poz e la distanta minima fata de sursa
       // {
          //parcurgem lista de adiacenta a lui poz
          for(i=0;i<L[poz].size();i++)
            if(D[L[poz][i].first]>D[poz]+L[poz][i].second ) //daca putem imbunatati distanta
            {
                D[L[poz][i].first]=D[poz]+L[poz][i].second;
                coada.push(make_pair(L[poz][i].first,D[L[poz][i].first]));
                   //adaugam nodul si distanta imbunatatita in coada
            }
        //}
    }

}

int main()
{
   int x,y,c,i;
   f>>n>>m;
   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;
}