#include <fstream>
#include<queue>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<climits>
#include<deque>
#include<unordered_map>
#include<unordered_set>
using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const int inf=1e9;
int dist[50001];
int main()
{
  int n,m;
  cin>>n>>m;
  vector<vector<pair<int,int>>>no(50001);
  for(int i=0;i<m;i++){
    int n1,n2,cos;
    cin>>n1>>n2>>cos;
    no[n1].push_back({n2,cos});
  }
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
  for(int i=1;i<=n;i++){
    dist[i]=inf;
  }
  int sc=1;
  dist[sc]=0;
  pq.push({0,sc});
  while(!pq.empty()){
    int dis=pq.top().first;
    int nod=pq.top().second;
    pq.pop();
    if(dis>dist[nod])continue;

    for(int i=0;i<no[nod].size();i++){
        int nd=no[nod][i].first;
        int cs=no[nod][i].second;
        if(dist[nd]>dist[nod]+cs){
            dist[nd]=dist[nod]+cs;
            pq.push({dist[nd],nd});
        }
    }
  }
  for(int i=2;i<=n;i++){
    if(dist[i]==inf)cout<<"0 ";
    else cout<<dist[i]<<" ";
  }
  return 0;
}