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

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

long long D[N];

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

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


int n,m;;
bool S[N];
vector <vector< pair< int, int> > >L(N);

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

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

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

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

    while(!coada.empty())
    {
        //extragem nodul aflat al distanta minima fata de r
        poz=coada.top();coada.pop();
        if(S[poz]==0)
        {
       //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(L[poz][i].first);   //adaugam nodul in coada
            }
         S[poz]=1;
        }
    }

}

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;
}