#include <fstream>
#include <iostream>
#include <utility>
#include <algorithm>
#include <set>
#include <climits>
#include <vector>
#define nmax 250005
 
using namespace std;
 
vector < pair <int,int> > v[nmax];
set <pair <int,int> > q;
int n,m;
int d[nmax];
 
void Push();
void Dijkstra();
 
int main(){
  ios_base::sync_with_stdio(false);
  int x,y,cost;
  ifstream cin("dijkstra.in");
  ofstream cout("dijkstra.out");
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    cin>>x>>y>>cost;
    v[x].push_back(make_pair(y,cost));
  }
  Dijkstra();
      for(int i=2;i<=n;i++)
	cout<<(d[i]==INT_MAX?0:d[i])<<' ';
  return 0;
}
 
inline void Push(int x,int new_d){
  set <pair <int,int> > ::iterator it=q.find(make_pair(d[x],x));
  if(it!=q.end()) q.erase(it);
  q.insert(make_pair(new_d,x));
  d[x]=new_d;
}
 
 
inline void Dijkstra(){
  int now;
  for(int i=0;i<=n;i++)
    d[i]=INT_MAX;
  Push(1,0);
  while(!q.empty()){
    now=q.begin()->second;
    q.erase(q.begin());
    for(int i=0;i<v[now].size();i++){
      int next=v[now][i].first;
      int cost=v[now][i].second;
      if(d[now]+cost<d[next])
        Push(next,d[now]+cost);
    }
  } 
}