#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int MAXN = 50005;
const int INF = 50000011;

int N, M, NH;
int H[MAXN], poz[MAXN], d[MAXN];
vector < pair <int, int> > G[MAXN];

inline void sterge();
inline void schimba(int, int);
inline void adauga(int);
inline void urca(int);
inline void coboara(int);

inline void sterge(int p)
{
    schimba(p, NH--);
    coboara(p);
}

inline void coboara(int p)
{
    int fiu_st = 2*p, fiu_dr = 2*p + 1, bun = p;
    if ( fiu_st <= NH && d[H[fiu_st]] < d[H[bun]] )
        bun = fiu_st;
    if ( fiu_dr <= NH && d[H[fiu_dr]] < d[H[bun]] )
        bun = fiu_dr;
    if ( bun != p )
    {
        schimba(bun, p);
        coboara(bun);
    }
}

inline void schimba(int p1, int p2)
{
    swap(H[p1], H[p2]);
    poz[H[p1]] = p1;
    poz[H[p2]] = p2;
}

inline void urca(int p)
{
    if ( p == 1 || d[H[p/2]] <= d[H[p]] )
        return;
    schimba(p, p/2);
    urca(p/2);
}

inline void adauga(int nod)
{
    H[++NH] = nod;
    poz[nod] = NH;
    urca(NH);
}

void read()
{
    int x, y, cost;

    fin >> N >> M;
    for (int i = 0; i < M; ++i)
    {
        fin >> x >> y >> cost;
        G[x].push_back(make_pair(y, cost));
    }
}

void initializeaza()
{
    for (int i = 2; i <= N; ++i)
        d[i] = INF;
    d[1] = 0;
}

void solve()
{
    adauga(1);

    while ( NH )
    {
        int nod_cr = H[1];
        sterge(1);

        int L = G[nod_cr].size();
        for (int i = 0; i < L; ++i)
        {
            int fiu = G[nod_cr][i].first;
            if ( d[nod_cr] + G[nod_cr][i].second < d[fiu] )
            {
                d[fiu] = d[nod_cr] + G[nod_cr][i].second;
                if ( poz[fiu] == 0 )
                    adauga(fiu);
                urca(poz[fiu]);
            }
        }
    }
}

void print()
{
    for (int i = 2; i <= N; ++i)
    {
        if ( d[i] == INF )
            fout << "0 ";
        else
            fout << d[i] << " ";
    }
}

int main ()
{
    read();
    initializeaza();
    solve();
    print();

    fin.close();
    fout.close();

    return 0;
}