#include <fstream>
#include <vector>
#include <queue>
#define NMAx 50100
#define inf 1<<28
using namespace std;
vector <unsigned short> G[NMAx],Cost[NMAx];
queue <unsigned short> q;
int n,dist[NMAx];
bool in_queue[NMAx];

void bf() {
	int i,nod,vecin,cost;
	q.push(1);
	while(!q.empty()) {
		nod=q.front();
		q.pop();
		in_queue[nod]=false;
		for(i=0;i<G[nod].size();i++) {
			vecin=G[nod][i];
			cost=Cost[nod][i];
			if(dist[nod]+cost<dist[vecin]) {
				dist[vecin]=dist[nod]+cost;
				if(!in_queue[vecin]) {
					q.push(vecin);
					in_queue[vecin]=true;
					}
				}
			}
		}
}
void citire() {
	
	int i,x,y,c,m;
	ifstream in("dijkstra.in");
	in>>n>>m;
	for(i=0;i<m;i++) {
		in>>x>>y>>c;
		G[x].push_back(y);
		Cost[x].push_back(c);
		}
	for(i=2;i<=n;i++)
		dist[i]=inf;
	in.close();
	
}
void afis() {
	
	int i;
	ofstream out("dijkstra.out");
	for(i=2;i<=n;i++)
		out<<dist[i]<<' ';
	out<<'\n';
	out.close();
	
}
int main() {
	
	citire();
	bf();
	afis();
	
	return 0;
	
}