#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

#define vii vector<pair<int, int> > 


struct cmp{
  bool operator()(const pair<int,int>& p1, const pair<int, int>& p2) {
    return p1.second > p2.second;
  }
};

vector<pair<int, int> > adj[50001];
priority_queue<pair<int, int>, vii, cmp > Q;

int main() {
  vector<int> graph(50001, 0x7fffffff);
  
  ifstream fin ("dijkstra.in");
  ofstream fout("dijkstra.out");
  int N,M; fin >> N >> M;
  for(int i = 0; i < M; ++i) {
    int node1, node2, cost; fin >> node1 >> node2 >> cost;
    adj[node1].push_back(make_pair(node2, cost));
  }
  int len1 = adj[1].size();
  for(int i = 0; i < len1; ++i) {
    Q.push(make_pair(adj[1][i].first, adj[1][i].second));
  }
  graph[1] = 0;
  while(!Q.empty()) {
    pair<int, int> nextEdge = Q.top(); Q.pop();
    //    cout << "neCost:" << nextEdge.second << " neNode:" << nextEdge.first << "| comp with g[ne]:" << graph[nextEdge.first] << "\n"; 
    if(nextEdge.second < graph[nextEdge.first]) {
      graph[nextEdge.first] = nextEdge.second;
      for(auto it = adj[nextEdge.first].begin(); it != adj[nextEdge.first].end(); ++it) {
	int nextCost = graph[nextEdge.first] + it->second;
	Q.push(make_pair(it->first, nextCost));
      } 
    }
    /*    cout << "graph:";
	  for(int i = 1; i <= N; ++i) {
	  cout << " " << graph[i];
	  }
	  cout << "\n";
    */
  }
  
  if(graph[2] != 0x7fffffff) {
    fout << graph[2];
  }
  else {
    fout << 0;
  }
  for(int i = 3; i <= N; ++i) {
    if(graph[i] != 0x7fffffff) {
      fout << " " << graph[i];
    }
    else {
      fout << 0;
    }
  }
  fout << "\n";
  
  return 0;
}