#include <fstream>	
#include <vector>
#include <functional>
#include <bits/stdc++.h>
#define nmax 50005
#define inf 0x3f3f3f3f
	
 
	
using namespace std;
	

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
	
	
class graf{	
private:
	vector<pair<int,int>> edges[nmax];
	
    int nodes;
	
public:
	
	graf(int n){
	
		nodes=n;
	
	}
	
	void addedge(int x,int y, int cost){
	
		edges[x].push_back({y,cost});
	
		//edges[y].push_back({x,cost});
	
	}
	
	void dijkstra(int source){
	
		priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int> >> hashmap;
		vector<int> dist(nodes+1,inf);
		vector<bool> visited(nodes+1, false);
	
		int nod, v, w, i;
	
		dist[source]=0;
	
		vector<pair<int,int>>::iterator it;
	
		hashmap.push({0,source});
	
			while(!hashmap.empty()){
	
				  nod=hashmap.top().second;
	
				  hashmap.pop();
	
				  if(visited[nod])
	
				  	 continue;
	
				  	visited[nod]=true;
	
				  for(it=edges[nod].begin();it!=edges[nod].end();it++){
	
				  	 v=it->first;
	
				  	 w=it->second;
	
				  	 if(dist[v] > dist[nod]+w){
	
				  	 	dist[v]=dist[nod]+w;
	
				  	 	hashmap.push({dist[v],v});
	
				  	 }
	
				  }
	
			}
	
		for(i=2;i<=nodes;i++)
	
			if(dist[i]==inf)
	
			g<<0<<" ";
	
		else
	
			g<<dist[i]<<" ";
	
	}	
};
	
int main(){
	
	int x, y, cost, n, m, i;
	
	f>>n>>m;
	
	graf graph(n);
	
	for(i=1;i<=m;i++){
	
		f>>x>>y>>cost;
	
		graph.addedge(x,y,cost);
	
	}
	
  graph.dijkstra(1);
	
  return 0;
	
}