#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0);
#define tie cin.tie(0);
#define mp make_pair
#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define zeros(x) ( (x ^ (x - 1)) & x )
# define INF 0x3f3f3f3f
   
using namespace std;

set < PII > S;
vector < int > D(50100, INF);
vector < PII > V[50100];
int n, m, x, y, cost;

void dijkstra(int x)
{
	S.insert(mp(0, x));
	D[x] = 0;
	while (S.size())
	{
		int curr = S.begin()->second;
		S.erase(S.begin());
		for (auto it : V[curr])
		{
			int vertex = it.first;
			int weight = it.second;
			if (D[vertex] > D[curr] + weight)
			{
				if (D[vertex] != INF)
					S.erase(S.find(mp(D[vertex], vertex)));
				D[vertex] = D[curr] + weight;
				S.insert(mp(D[vertex], vertex));
			}
		}
	}
}

int main(){
    IOS tie
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
	{
		cin >> x >> y >> cost;
		V[x].push_back(mp(y, cost));
	}
	dijkstra(1);
	for (int i = 2; i <= n; i++)
		cout << (D[i] == INF ? 0 : D[i]) << " ";
    
    cerr << "Fucking time elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}