#include<cstdio>
#include<cstring>
#include<set>
#include<vector>

using namespace std;

#define pb push_back
#define mp make_pair
#define Nmax 50001
#define INF 0x3f3f3f3f

int N, M, D[Nmax]; 
vector<pair<int, int> > G[Nmax];
set<pair<int, int> > T;

void dijkstra() {
    int i, val, x, cost, nod;
    vector<pair<int, int> > :: iterator it, itend;
	set<pair<int, int> > :: iterator it2;
    memset(D,INF,sizeof(D)); D[1]=0; T.insert(mp(0,1));
	while(!T.empty()) {
        it2=T.begin(); val=it2->first; x=it2->second; T.erase(it2);
		for(it=G[x].begin(), itend=G[x].end(); it!=itend; ++it) {
			nod=it->first; cost=it->second;
			if(D[nod]>val+cost) {
				if(D[nod]!=INF)
					T.erase(mp(D[nod],nod));
				D[nod]=val+cost;
				T.insert(mp(D[nod],nod));
			}
		}
	}
}

int main() {
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
	int i, j, cost;
	scanf("%d %d\n",&N,&M);
	while(M--) {
        scanf("%d %d %d\n",&i,&j,&cost); 
		G[i].pb(mp(j,cost));
	}
	dijkstra();
	for(i=2; i<=N; ++i)
        printf("%d ",D[i]==INF ? 0 : D[i]);
	return 0;
}