#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
#define inf INT_MAX
#define DIM 50010
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,x,y,z,i,d[DIM],v[DIM],ciclu[DIM];
vector< pair<int,int> > L[DIM];
queue<int> q;
int main() {
	fin>>n>>m;
	for (i=1;i<=m;i++) {
		fin>>x>>y>>z;
		L[x].push_back({y,z});
	}
	q.push(1);
	v[1]=1; d[1]=0;
	for (i=2;i<=n;i++)
		d[i]=inf;
	while (!q.empty()) {
		x=q.front();
		q.pop();
		v[x]=0;
		for (i=0;i<L[x].size();i++) {
			y=L[x][i].first;
			int cost=L[x][i].second;
			if (d[y]>d[x]+cost) {
				d[y]=d[x]+cost;
				if (v[y]==0) {
					ciclu[y]++;
					if (ciclu[y]==n) {
						break;
					}
				}
				q.push(y);
				v[y]=1;
			}
		}
	}
	for (i=2;i<=n;i++) {
		if (d[i]==inf)
			fout<<"0 ";
		else
			fout<<d[i]<<" ";
	}
	return 0;
}