#include<bits/stdc++.h>
#define NMAX 50005
#define s second
#define f first

using namespace std;

const int inf=(1<<30);

int n,m,x,y,c;
int d[NMAX];
bool inQ[NMAX];



struct comp {
	bool operator() (int x, int y) {
		return d[x]>d[y];
	}
};

priority_queue <int, vector<int>, comp> Q;
vector <pair<int,int> >V[NMAX];

void Dijkstra(int start){
	
	for (int i=1; i<=n; i++) {
		d[i]=inf;
	}
	
	d[start]=0;
	
	Q.push(start);
	inQ[start]=1;
	while (!Q.empty()) {
		
		int cost,y;
		x = Q.top(); Q.pop();
		inQ[x] = 0;
		
		for (int i=0; i<V[x].size(); i++) {
			cost = V[x][i].s;
			y = V[x][i].f;
			if (cost+d[x]<d[y]) {
				d[y] = cost+d[x];
				
				if (!inQ[y]) Q.push(y), inQ[y]=1;
			}
		}
		
	}
}

int main() {
	ifstream cin("dijkstra.in");
	ofstream cout("dijkstra.out");
	cin>>n>>m;
	
	for (int i=0; i<m; i++) {
		cin>>x>>y>>c;
		
		V[x].push_back(make_pair(y,c));
	}
	
	Dijkstra(1);
	
	for (int i=2; i<=n; i++) {
		if (d[i]==inf) cout<<"0 ";
		else cout<<d[i]<<' ';
	}
	
	
	
	return 0;
}