#include <fstream>
#include <vector>
#include <algorithm>

#define NLen 0x10000
#define inf 0x7fffffff

#define adj first
#define cost second

using namespace std;

ifstream fi;
ofstream fo;

vector < pair < int, int > > G[NLen];

int DIST[NLen];
int H[NLen];
int POS[NLen];

int N;

inline void Up_Heap(int nod)
{
    int Aux = H[nod];

    for(; nod > 1 && DIST[ H[nod] ] < DIST[ H[nod >> 1] ]; nod >>= 1)
    {
        H[nod] = H[nod >> 1];
        POS[ H[nod] ] = nod;
    }

    H[nod] = Aux;
    POS[Aux] = nod;
}

inline void Down_Heap()
{
    int nod = 1, L, R;
    int Aux = H[nod];

    while(1)
    {
        L = nod << 1;
        R = L + 1;

        if(R <= H[0] && DIST[ H[L] ] > DIST[ H[R] ] && DIST[ H[L] ] < DIST[Aux])
        {
            H[nod] = H[R];
            POS[ H[nod] ] = nod;
            nod = R;
        }
        else
        if(L <= H[9] && DIST[ H[L] ] < DIST[Aux])
        {
            H[nod] = H[L];
            POS[ H[nod] ] = nod;
            nod = L;
        }
        else
        {
            H[nod] = Aux;
            POS[Aux] = nod;
            return;
        }
    }
}

inline void Pop_Heap()
{
    if(H[0] == 1)
    {
        H[0] = 0;
        return;
    }

    H[1] = H[ H[0] -- ];
    POS[ H[1] ] = 1;

    Down_Heap();
}

inline void dij(int nod)
{
    for(int i = 1; i <= N; ++ i)
    {
        DIST[i] = inf;
        H[i] = i;
        POS[i] = i;
    }

    H[0] = N;
    H[nod] = 1;
    POS[1] = nod;

    H[1] = nod;
    POS[nod] = 1;

    DIST[nod] = 0;

    while(H[0])
    {
        nod = H[1];
        Pop_Heap();

        for(int i = 0; i < G[nod].size(); ++ i)
            if(DIST[ G[nod][i].adj ] == inf || DIST[ G[nod][i].adj ] > DIST[nod] + G[nod][i].cost)
            {
                DIST[ G[nod][i].adj ] = DIST[nod] + G[nod][i].cost;
                Up_Heap(POS[ G[nod][i].adj ]);
            }
    }
}

int main()
{
    int M, x, y, c;

    fi.open("dijkstra.in");

    fi >> N >> M;
    for(; M -- ; )
    {
        fi >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }

    fi.close();

    dij(1);

    fo.open("dijkstra.out");

    for(int i = 2; i <= N; ++ i)
        if(DIST[i] == inf) DIST[i] = 0;
    for(int i = 2; i <= N; ++ i)
        fo << DIST[i] << ' ';
    fo << '\n';

    fo.close();

    return 0;
}