#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

#define pb push_back
#define N 50005
#define INF 2000000000
queue<int> q;
typedef pair <int, int> graf;
vector <graf> v[N];
int nr[N],sol[N],f[N],n,m;
int main(){
	int x,y,z,nod,nxt,cst,i;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d", &n, &m);
	for(int i=1; i<= n ; i++){
		scanf("%d%d%d",&x,&y,&z);
		v[x].pb(graf(y, z));
		nr[x]++;
	}
	for(i=2;i<=n;i++)
		sol[i]=INF;
	q.push(1);
	f[1]=1;
	while(!q.empty()){
		nod=q.front();
		q.pop();
		
		for(i=0;i<nr[nod]; i++){
			nxt=v[nod][i].first;
			cst=v[nod][i].second;
			
			if(sol[nod]+cst<sol[nxt]){
				sol[nxt]=sol[nod]+cst;
				
				if(!f[nxt]){
					q.push(nxt);
					f[nxt]=1;
				}
			}
		}
		f[nod]=0;
	}
	for(i=2;i<=n;i++)
		printf("%d ",sol[i]!=INF ? sol[i] : 0);
	return 0;
}