#include <bits/stdc++.h>
#define inf 2e9
#define N 50005

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

priority_queue<pair<int,int> >q;
vector<pair <int,int> >v[N];

int n, m, x, y, cost, d[N], nod;

void dijkstra(){

	q.push({0,1});

	d[1]=0;

	while(!q.empty()){

		nod = q.top().second;
		cost = -q.top().first;

        q.pop();

        if(d[nod] != 0 && d[nod] != inf){
			continue;
        }

        d[nod] = cost;

        for(auto  i:v[nod]){

			if(d[i.second] > cost + i.first){
				q.push({-(cost + i.first), i.second});
			}
        }

	}
}

int main()
{
    fin >> n >> m;

	for(int i = 1; i <= m; i++){

		fin >> x >> y >> cost;

		v[x].push_back({cost,y});
	}

	for(int i = 2; i <= n; i++)
        d[i] = inf;

    dijkstra();

	for(int i = 2; i <= n; i++){

        if(d[i] != inf)
            fout << d[i] << ' ';
        else
            fout << 0 << ' ';
    }

    return 0;
}