#include <cstdio>
#include <vector>
#include <set>
#define mp make_pair
#define INF 999999999
using namespace std;
int i, cost, x, y, N, M, Drum[50100];
vector< pair<int, int> > G[50100];
void dijkstra()
{
    set< pair<int,int> > H;
    vector<pair< int, int > >::iterator it;
    int nrAdaugat=0;
    H.insert(mp(0,1));
    while (! H.empty() )
    {
        int cost=(*H.begin()).first, y=(*H.begin()).second;
        H.erase ( H.begin() );
        for (it=G[y].begin(); it!=G[y].end(); it++)
        if (cost+(*it).first< Drum[(*it).second])
                Drum[(*it).second]=cost+(*it).first, H.insert( mp( Drum[(*it).second], (*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].push_back(mp( cost, y));
    }
    for (i=2; i<=N; i++) Drum[i]=INF;
    Drum[1]=0;
    dijkstra();
    for (i=2; i<=N; i++) if (Drum[i]!=INF) printf("%d ", Drum[i]); else printf("0 ");
    return 0;
}