//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m;
const int Max =50005;
vector < pair < int ,int > >v[Max];
set < pair < int , int > >c;
bool t[Max];
int d[Max];
void citire()
{
  in>>n>>m;
  for(int i=0;i<m;i++)
  {
      int x,y,z;
      in>>x>>y>>z;
      v[x].push_back(make_pair(y,z));
  }
  for(int i=2;i<=n;i++)
    d[i]=INT_MAX;
    d[1]=0;
    c.insert({0,1});

}
void Dijkstra()
{
    while(!c.empty())
    {
        int nod=c.begin()->second;
        c.erase(c.begin());
        t[nod]=1;
     for(int i=0;i<v[nod].size();i++)
     {
         int vecin=v[nod][i].first;
         int dist=v[nod][i].second;
         if( t[vecin]==0 && d[vecin]>d[nod]+dist)
         {
             if(d[vecin]!=INT_MAX)
             c.erase({d[vecin],vecin});
             d[vecin]=d[nod]+dist;
                c.insert({d[vecin],vecin});

         }
     }
    }



}
void afisare()
{
    for(int i=2;i<=n;i++)
        if(d[i]!=INT_MAX)
        out<<d[i]<<" ";
    else
        out<<0<<" ";
}
int main()
{
    citire();
    Dijkstra();
    afisare();
    return 0;
}