#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

#define MN (50000)
#define INF (50000001) // MN*1000+1 with 1000 being the maximum cost of an edge

vector<int> g[MN]; // graph
vector<int> c[MN]; // cost
int d[MN]; // distance
bool v[MN]; // visited
int N; // number of nodes
int M; // number of edges

class cmp {
public:
	bool operator()(const int &n1, const int &n2)
	{
		return d[n1] > d[n2];
	}
};

priority_queue<int, vector<int>, cmp> q;

void dijkstra(int startNode)
{
	int i, n1, n2;
	for(i = 0; i < N; ++i) {
		d[i] = INF;
		v[i] = 0;
	}
	for(q.push(startNode), d[startNode] = 0; !q.empty(); q.pop()) {
		n1 = q.top();
		if(v[n1])
			continue;
		//printf("Using %d with %d\n", n1, n1d);
		v[n1] = 1;
		for(i = 0; i < g[n1].size(); ++i) {
			n2 = g[n1][i];
			if(d[n1]+c[n1][i] < d[n2]) {
				d[n2] = d[n1]+c[n1][i];
				q.push(n2);
			}
		}
	}
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	int i, A, B, C;

	scanf("%d %d", &N, &M);

	for(i = 0; i < M; ++i) {
		scanf("%d %d %d", &A, &B, &C); --A; --B;
		g[A].push_back(B);
		c[A].push_back(C);
	}

	dijkstra(0);

	for(i = 1; i < N; ++i)
		printf("%d ", d[i] == INF? 0 : d[i]);

	return 0;
}