#include<bits/stdc++.h>
using namespace std;

ifstream fin ("date.in");
ofstream fout ("date.out");
int n, m, x, y, w;
vector<vector<pair<int, int>>> graf;
vector<int> dist;
vector<int> tata;
vector<int> viz;
int main()
{
    fin >> n >> m;

    for (int i=0; i<=n; ++i) {
        vector<pair<int, int> > aux;
        graf.push_back(aux);
        dist.push_back(20001);
        tata.push_back(0);
        viz.push_back(0);
    }


    for (int i=1; i<=m; ++i) {
        fin >> x >> y >> w;
        pair <int, int> p;
        p.first=y;
        p.second=w;
        graf[x].push_back(p);
    }

  	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
  	//w,v
  	pq.push(make_pair(0, 1));
  	dist[1]=0;

		while(!pq.empty()) {
			int u = pq.top().second;
			pq.pop();
			viz[u] = 1;
			for(int i = 0; i < graf[u].size(); i++) {
				int v = graf[u][i].first;
				w = graf[u][i].second;
				if  (viz[v] == 0 && dist[v] > dist[u] + w) {
					dist[v] = dist[u] + w;
					pq.push(make_pair(dist[v], v));
				}
			}
		}
    for (int i=2; i<=n; ++i) {
    		if (dist[i] == 20001)
    			fout << 0 << " ";
    		else
        	fout << dist[i] << " ";
    }

    return 0;
}