#include <fstream>
#include <vector>
#include <set>
#define INF 1000000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<  pair<int, long long>   > v[50002];
set < pair< long long , int> > s; // scoate minimul
long long d[50002];

int main()
{
  int n,m, a, b, c;
  fin>>n>>m;
  for(int i=1;i<=m;i++){
    fin>>a>>b>>c; // a--cost c->b
    v[a].push_back( make_pair(b, c) );
  }

  for(int i=1;i<=n;i++){
    d[i] = INF;
  }
  d[1]=0;
  s.insert( make_pair(0,1) );

  while( !s.empty() ){
    int nod = s.begin()->second;
    long long dist = s.begin()->first; // s[nod]=1;
    s.erase( s.begin() );
    for(vector<pair<int, long long>> :: iterator it = v[nod].begin(); it != v[nod]. end(); it++){
      int vecin = it -> first;
      long long dist_vecin = it -> second;
      if(dist + dist_vecin < d[vecin]){
        // ( d[vecin], vecin) scoatem si bagam (dist + dist_vecin, vecin)
        if( s.find( make_pair(d[vecin], vecin) ) != s.end())
                      s.erase( s.find(make_pair(d[vecin], vecin)) ) ;
        s.insert( make_pair(dist + dist_vecin, vecin) );
        d[vecin] = dist + dist_vecin, vecin;
      }
    }

  }

  for(int i=2; i<=n; i++)
    if(d[i]==INF)fout<<0<<' ';
        else fout<<d[i]<<' ';

  return 0;
}