#include <stdio.h>
#include <queue>
#include <vector>
#define INFINITY 50000001;
using namespace std;


typedef struct{
	int node;
	long dist;
}nodeDistPair;

bool operator<(nodeDistPair n1,nodeDistPair n2){return n1.dist<n2.dist;}
bool operator>(nodeDistPair n1,nodeDistPair n2){return !(n1<n2);}

priority_queue <nodeDistPair,vector<nodeDistPair>, less<nodeDistPair> > pq;

//priority_queue<>
int m,n;
vector<long> dist;
vector< vector<int> > G;
vector< vector<int> > C;

int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	int x,y,c;
	scanf("%d",&n);scanf("%d",&m);
	for(int i=0;i<=n;i++){vector<int> gv;vector<int> cv;C.push_back(cv);G.push_back(gv);dist.push_back(50000006);}
	dist[1]=0;
	for(int i=0;i<m;i++){
		scanf("%d",&x);
		scanf("%d",&y);
		scanf("%d",&c);
		G[x].push_back(y);
		C[x].push_back(c);
	}
	nodeDistPair first;
	first.node=1;
	first.dist=0;
	pq.push(first);

	while(!pq.empty()){
	
		nodeDistPair p = pq.top();pq.pop();
		if(dist[p.node]!=p.dist)continue;

		for(int i = 0;i<G[p.node].size();i++){
			if(dist[G[p.node][i]]> dist[p.node]+C[p.node][i]){
				dist[G[p.node][i]]=dist[p.node]+C[p.node][i];
				nodeDistPair newP;newP.node=G[p.node][i];newP.dist=dist[G[p.node][i]];
				pq.push(newP);
			}
			
		}

	}

	for(int i=2;i<=n;i++)
		printf("%ld ",dist[i]);
	return 0;
}