//#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];
queue < 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.push(1);

}
void Dijkstra()
{
    while(!c.empty())
    {
        int nod=c.front();
     c.pop();
     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)
         {
             d[vecin]=d[nod]+dist;
             c.push(vecin);
         }
     }
    }



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