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

using namespace std;

const int INF = 50000010;
const int nm  = 50010;

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

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



int main()

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



	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].push_back(make_pair(b, c));
	}
	d[1] = 0;
    eq[1] = true;
	for (i=2; i<=n; ++i)
    {
		d[i] = INF;
        eq[i] = false;
	}


	q.push(1);

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

        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])
                {
                	q.push(it->first);
                    eq[it->first] = true;
                }
            }
        
    }
    

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



    fclose(stdin);
    fclose(stdout);

	return 0;
}