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

using namespace std;

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

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

void dijkstra() {
    int val, x, cost, nod;
    vector< pair<int, int> > :: iterator it;
	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(); it!=G[x].end(); ++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;
}