#include <cstdlib>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#define MAXN 100000 //maksymalna liczba wierzcholkow
#define INF 1000000000000001LL //nieskonczonosc
using namespace std;

vector<pair<int,long long> > kraw[MAXN+1];
vector<long long> waga[MAXN+1]; 
long long dis[MAXN+1];
int vis[MAXN+1];

void Dijkstra(int n) {
	priority_queue<pair<long long,int>,vector<pair<long long,int> >, greater<pair<long long,int> > > Q;
	vis[n]=1;
	Q.push(make_pair(0,n));
	while(!Q.empty()) {
		pair<long long,int> v=Q.top();Q.pop();
		if(!vis[v.second]) {
			dis[v.second]=v.first;
		 	vis[v.second]=1;
		}		
		for(int i=0;i<(int)kraw[v.second].size();i++)
		  	if(!vis[kraw[v.second][i].first])
		   		Q.push(make_pair(kraw[v.second][i].second+v.first,kraw[v.second][i].first));
	}
}

int n, m, a, b, c;

int main() {
	scanf("%d%d",&n,&m);
	while(m--) {
		scanf("%d%d%d",&a,&b,&c);
		kraw[b].push_back(make_pair(a,c));
	}
	for(int i=0;i<=n;i++)
		dis[i]=-1;
	Dijkstra(1);
	for(int i=2;i<=n;i++)
	    printf("%lld\n",dis[i]);	    
   return 0;
}
