#include<cstdio>
#include<set>
#include<vector>
#include<bitset>

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;
	bitset<Nmax> use;
    for(i=2; i<=N; i++)
		D[i]=INF;
    use[1]=1; 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) {
				D[nod]=val+cost;
				if(!use[nod]) {
					T.insert(mp(D[nod],nod));
					use[nod]=1;
				}
			}
		}
	}
}

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;
}