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

using namespace std;

#define INF 50000010
#define nm 50010
#define mp make_pair
#define pb push_back

int n, m, i, j;
int a, b, c;
int d[nm];
int eq[nm];

queue <int> q;
vector < pair <int, int> > v[nm];
vector < pair <int, int> > :: iterator it;




void read()

{
	//scanf("%d %d ", &n, &m);
    cin >> n >> m;
	for (i=1; i<=m; ++i)
	{
		//scanf("%d %d %d", &a, &b, &c);
        cin >> a >> b >> c;
		v[a].pb(mp(b, c));
	}
	d[1] = 0;
    eq[1] = 1;
	for (i=2; i<=n; ++i)
    {
		d[i] = INF;
        eq[i] = 0;
	}

}


void solve()

{
	q.push(1);

    while (!q.empty())
    {
    	a = q.front();
        q.pop();
        eq[a] = 0;

        for (it=v[a].begin(); it!=v[a].end(); ++it)
        	if (d[it->first] > d[a] + it->second)
            {
        		d[it->first] = d[a] + it->second;
                if (eq[it->first]==0)
                {
                	q.push(it->first);
                    eq[it->first] = 1;
                }
            }
        
    }
    
}


void write()

{
	for (i=2; i<=n; ++i)
	{
		if (d[i] == INF)
			d[i] = 0;
		//printf("%d ", d[i]);
        cout << d[i] << " ";
	}
//	printf("\n");
}


int main()

{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out","w",stdout);

	read();
	solve();
	write();

    fclose(stdin);
    fclose(stdout);

	return 0;
}