#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];
///////////////////////
#define MaxBuffer 8192
char buffer[MaxBuffer];
int bufferIndex=8191;
///////////////////////

inline void read_buffer(istream& in,int& x) {
	do {if(++bufferIndex==MaxBuffer) {
		bufferIndex=0;
		in.read(buffer,MaxBuffer);
		}
	}while( buffer[bufferIndex]<'0'||buffer[bufferIndex]>'9' );
 
	for(x=0;buffer[bufferIndex]>='0'&&buffer[bufferIndex]<= '9';) {
		x=x*10+buffer[bufferIndex]-'0';
		if(++bufferIndex==MaxBuffer) {
			bufferIndex=0;
			in.read(buffer,MaxBuffer);
			}
		}
}
void bf() {
	int i,nod,vecin;
	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];
			if(dist[nod]+Cost[nod][i]<dist[vecin]) {
				dist[vecin]=dist[nod]+Cost[nod][i];
				if(!in_queue[vecin]) {
					q.push(vecin);
					in_queue[vecin]=true;
					}
				}
			}
		}
}
void citire() {
	
	int i,x,y,c,m;
	ifstream in("dijkstra.in");
	read_buffer(in,n);
	read_buffer(in,m);
	//in>>n>>m;
	for(i=0;i<m;i++) {
		//in>>x>>y>>c;
		read_buffer(in,x);
		read_buffer(in,y);
		read_buffer(in,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++)
		if(dist[i]==inf)
			out<<"0 ";
		else
			out<<dist[i]<<' ';
	out<<'\n';
	out.close();
	
}
int main() {
	
	citire();
	bf();
	afis();
	
	return 0;
	
}