#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define N 50001
#define oo 0x3f3f3f3f

using namespace std;

int d[N], n, m;

struct cmp{
    bool operator()(const int &a, const int &b)const // devine min heap 
    {
                if(d[a]>d[b])return 1;
                return 0;
    }
};

vector<pair<int, int> > a[N]; // lista de adiacenta

priority_queue<int, vector<int>, cmp> Q;

void read() {
	freopen("dijkstra.in", "r", stdin);
	cin>>n; //nr noduri
	cin>>m; // nr de arce
	
	for (int i=1; i<=m; i++) {
		int x, y, c;
		cin>>x>>y>>c;

		a[x].push_back(make_pair(y,c));
	}
}

void dijkstra() {
	d[1]=0;
	for (int i=2; i<=n; i++)
		d[i]=oo;
	Q.push(1); // nodul 1 in coada

	while (!Q.empty()) {
		int u = Q.top(); // ia nodul cu distanta minima in logn
		Q.pop();
		for (int k=0; k<a[u].size(); k++) {
			if (d[u]+a[u][k].second < d[a[u][k].first]) {
				d[a[u][k].first]=d[u]+a[u][k].second;
				Q.push(a[u][k].first);
			}
		}
	}
}

void print() {
	freopen("dijkstra.out", "w", stdout);
	int i;  
    for(i=1;i<=n;++i) if(d[i]==oo) d[i]=0; 
	for (int i=2; i<=n; i++)
		cout<<d[i]<<" ";
}

int main() {
	read();
	dijkstra();
	print();

	return 0;

}