#include <fstream>
#include <vector>
#include <iostream>
#include <string.h>
#include <utility>
#include <set>
#define pb push_back
#define mp make_pair
#define TR(C, i)\
    for(i = C.begin(); i != C.end(); i++)

using namespace std;

const int nmax = 50010;
int N, M;
vector< pair<int, int> > G[nmax];

void read()
{
    int i, a, b, c;
    ifstream in("dijkstra.in");
    in>> N >> M;
    for(i = 1; i <= M; i++)
    {
        in >> a >> b >> c;
        G[a].pb(mp(b,c));
    }
}

const int oo = 0x6f6f6f6f;
int D[nmax], InH[nmax];
set< pair <int, int> > H;

void solve()
{
    //pairu din set tine minte D si N (nodu)
    //deci first va fi dist
    memset(D, oo, sizeof(D));
    D[1] = 0;
    H.insert(mp(0,1));
    InH[1] = 1;
    int dist, nod;
    vector< pair<int, int> >::iterator it;
    set< pair<int, int> >::iterator F;
    while(!H.empty())
    {
        dist = (*H.begin()).first;
        nod = (*H.begin()).second;
        InH[nod] = 0;
        H.erase(H.begin());

        TR(G[nod], it)
            if(dist + it->second < D[it->first])
            {
                if(InH[it->first])
                {
                    F = H.find( mp(D[it->first],it->first) );
                    D[it->first] = it->second + dist;
                    H.erase(F);
                    H.insert( mp(D[it->first], it->first) );
                }
                else {
                    InH[it->first] = 1;
                    D[it->first] = it->second + dist;
                    H.insert( mp(D[it->first], it->first) );
                }
            }
    }
    freopen ("dijkstra.out", "w", stdout);
    for(dist = 2; dist <= N; dist++)
        if(D[dist] == oo)
            printf("0 ");
        else printf("%d ", D[dist]);
}


int main()
{
    read();
    solve();
    return 0;
}