#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cstring>

using namespace std;

//#include <iostream>
#include <fstream>

//ifstream cin ("input.in");
//ofstream cout ("output.out");

ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");

static const int NMAX = 5e4+5;
static const int MMAX = 25e4+5;

class cmp {
public:
	const bool operator () ( const pair<int, int> &a, const pair<int, int> &b ) {
		return a.second > b.second;
	}
};

int n, m;

int v[NMAX];

vector <pair<int, int>> graph[MMAX];

priority_queue <pair<int, int>, vector<pair<int, int>>, cmp> pq;


void Dijkstra( int startVertex ) {

	pq.push({startVertex, 0});

	while ( pq.size() ) {
		int vertex = pq.top().first;
		int cost = pq.top().second;

		pq.pop();

		if ( v[vertex] != cost ) {
			continue;
		}

		for ( auto x:graph[vertex] ) {
			if ( v[x.first] > v[vertex]+x.second ) {
				v[x.first] = v[vertex]+x.second;
				pq.push({x.first, v[x.first]});
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin>>n>>m;

	for ( int i = 2; i <= n; ++i ) {
		v[i] = 1e9;
	}

	for ( int i = 1; i <= m; ++i ) {
		int a, b, c;

		cin>>a>>b>>c;
		graph[a].push_back({b, c});
	}

	Dijkstra(1);

	for ( int i = 2; i <= n; ++i ) {
		cout<<v[i]<<" ";
	}
}