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

using namespace std;

struct NodDist{
    int nod;
	int dist;

    // compare for order.     
    bool operator <(const NodDist & pt) const
    {
        return (dist < pt.dist) ;
    }
};

#define INF 1000000000

int M,N;

vector<NodDist> L[50000];
bool S[50000]; 
int D[50000];


set<NodDist> Q;

void dijkstra(){
	for(int i=1;i<N;i++)
		D[i]=INF; 
	D[0]=0; 
	
	NodDist x;
	x.nod=0;
	x.dist=0;
	Q.insert(x);

	int u;
	set<NodDist>::iterator itset;
	vector<NodDist>::iterator itvec; 

	while(!Q.empty()){
		itset = Q.begin();
		u=(*itset).nod;	
		S[u]=true;

		Q.erase(itset);

		int muchie,vecin;
		NodDist y;

		for (itvec = L[u].begin(); itvec != L[u].end(); ++itvec) {
			vecin=(*itvec).nod;
			muchie=(*itvec).dist;
			
			if(S[vecin]==false && D[u] + muchie < D[vecin]){
				D[vecin]=D[u]+muchie;
				y.nod=vecin;
				y.dist=D[vecin];
				Q.insert(y);
			}
		}
	}		
}



int main(){
	
	freopen("dijkstra.in","rt",stdin);
	freopen("dijkstra.out","wt",stdout);
	
	scanf("%d %d",&N,&M);

	int x,y,d;
	NodDist z;

	for(int i=0;i<M;i++){
		scanf("%d %d %d",&x,&y,&d);
		z.nod=y-1;
		z.dist=d;
		L[x-1].push_back(z);	
	}

	dijkstra();

	for(int i=1;i<N;i++){
		if(D[i]==INF)
			printf("0 ");
		else
			printf("%d ",D[i]);
	}

	return 0;
}