#include <cstdio>
#include <set>
#include <vector>
#define mp make_pair
#define pb push_back
#define INF 99999999
using namespace std;
int N, M, i, X, Y, Cost, COST[51000];
vector< pair<int, int> > G[51000];
void Dijkstra()
{
    vector< pair<int, int> >::iterator it;
    set< pair<int, int> > H;
    H.insert( mp(0, 1));
    while (!H.empty())
    {
        int nod=(*H.begin()).second, cost=(*H.begin()).first;
        H.erase( H.begin() );
        for (it=G[nod].begin(); it!=G[nod].end(); it++)
            if (cost+(*it).first<COST[(*it).second])
                COST[(*it).second]=cost+(*it).first, H.insert( mp(cost+(*it).first, (*it).second));
    }
}
int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d%d", &N, &M);
    for (i=1; i<=M; i++)
    {
        scanf("%d%d%d", &X, &Y, &Cost);
        G[X].pb( mp(Cost, Y));
    }
    for (i=1; i<=N; i++) COST[i]=INF;
    COST[1]=0;
    Dijkstra();
    for (i=2; i<=N; i++)
        if (COST[i]!=INF) printf("%d ", COST[i]); else printf("0 ");
    return 0;
}