#include <bits/stdc++.h>
using namespace std;

const long long INF=1e16;
const int NMAX=1e5;
vector<pair<int, int>> adj[NMAX+1];
int N;
long long dist[NMAX+1];
bool processed[NMAX+1];

void citire() {
	int M;
	cin>>N>>M;
	for(int i=1;i<=M;++i) {
		int a, b, c;
		cin>>a>>b>>c;
		adj[a].push_back(make_pair(b, c));
	}
}

void dijkstra() {
	for(int i=2;i<=N;++i) {
		dist[i]=INF;
	}
	priority_queue<pair<long long, int>> q;
	dist[1]=0;
	q.push(make_pair(0, 1));
	while(!q.empty()) {
		int a=q.top().second;
		q.pop();
		if(processed[a])	
			continue;
		processed[a]=true;
		for(auto v:adj[a]) {
			int b=v.first, c=v.second;
			if(dist[a]+c<dist[b]) {
				dist[b]=dist[a]+c;
				q.push(make_pair(-dist[b], b));
			}
		}
	}
}

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	citire();
	dijkstra();
	for(int i=2;i<=N;++i)
		cout<<dist[i]<<' ';
	return 0;
}