#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned ll
#define vec vector
#define flist forward_list
#define um unordered_map
#define us unordered_set
#define prioq priority_queue
#define all(x) x.begin(), x.end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define ld long double

#define LL_MAX LLONG_MAX
#define LL_MIN LLONG_MIN
#define ULL_MAX ULLONG_MAX
#define ULL_MIN 0
#define LD_MAX LDBL_MAX
#define LD_MIN LDBL_MIN

#define nline '\n'

#define vv(type, name, n, ...) vector<vector<type>> name(n, vector<type>(__VA_ARGS__))
#define vvv(type, name, n, m, ...)                                                                                     \
    vector<vector<vector<type>>> name(n, vector<vector<type>>(m, vector<type>(__VA_ARGS__)))

#define for1(n) for (ll i = 0; i < (ll)(n); ++i)
#define for2(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for3(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define for4(i, a, b, c) for (ll i = (ll)(a); i < (ll)(b); i += (c))
#define for1e(n) for (ll i = 1; i <= (ll)(n); ++i)
#define for2e(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define for3e(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define for4e(i, a, b, c) for (ll i = (ll)(a); i <= (ll)(b); i += (c))
#define forit(v) for (auto it = v.begin(); it != v.end(); it++)
#define forit2(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define forrit(v) for (auto it = v.rbegin(); it != v.rend(); it++)
#define forrit2(it, v) for (auto it = v.rbegin(); it != v.rend(); it++)

const ll MOD = 1e9 + 7;

const string FILENAME = "dijkstra";
ifstream fin(FILENAME + ".in");
ofstream fout(FILENAME + ".out");

#define cin fin
#define cout fout

void solve();

int main()
{
	ll n, m;
	
	cin >> n >> m;
	
	vec<flist<pair<ll, ll>>> adj(n + 1);
	
	for1(m)
	{
		ll a, b, c;
		
		cin >> a >> b >> c;
		
		adj[a].pf({b, c});
	}
	
	vec<bool> vis(n + 1, 0);
	vec<ll> dist(n + 1, INT_MAX);
	prioq<pair<ll, ll>, vec<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
	
	pq.push({0, 1});
	
	ll node, d;
	
	while(!pq.empty())
	{
		node = pq.top().se;
		d = pq.top().fi;
		pq.pop();
		
		if(vis[node]) continue;
		
		vis[node] = 1;
		
		ll j, dj;
		
		forit(adj[node])
		{
			j = (*it).fi;
			dj = (*it).se;
			
			if(vis[j]) continue;
			
			if(d + dj < dist[j])
			{
				pq.push({d + dj, j});
				dist[j] = d + dj;
			}
		}
	}
	
	for3e(i, 2, n)
		cout << dist[i] << ' ';
		
    return 0;
}

void solve()
{
	
}