#include <bits/stdc++.h>
using ll=long long;
#define S second
#define F first
#define endl '\n'
#define spid ios_base::sync_with_stdio(false);cin.tie(NULL);
const int mod=1e9+7;
const double pi=3.14159265359;
const int maxn=50001;
using namespace std;

int n,m,dist[maxn],chk[maxn];

vector<vector<pair<int,int>>> A(maxn,vector<pair<int,int>>());

multiset<pair<int,int>> B;

int main(){
	ifstream cin("dijkstra.in");
	ofstream cout("dijkstra.out");
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int c1,c2,c3;
		cin>>c1>>c2>>c3;
		c1--;
		c2--;
		A[c1].push_back({c2,c3});
	}
	dist[0]=0;
	for(int i=1;i<n;i++)dist[i]=1e9;
	B.insert({0,0});
	while(B.size()){
		auto it=B.begin();
		int i=it->S;
		B.erase(B.begin());
		if(chk[i])continue;
		chk[i]=1;
		for(int j=0;j<A[i].size();j++){
			if(chk[A[i][j].F])continue;
			dist[A[i][j].F]=min(dist[A[i][j].F],dist[i]+A[i][j].S);
			B.insert({dist[i]+A[i][j].S,A[i][j].F});
		}
	}
	for(int i=1;i<n;i++){
		if(dist[i]==1e9)cout<<0<<" ";
		else cout<<dist[i]<<" ";
		
	}
}