#include <fstream>
#include <cstring>
#include <vector>

#define NLen 0x10000
#define inf 0x7fffffff

using namespace std;

ifstream fi;
ofstream fo;

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

int DIST[NLen];
int HEAP[NLen];
int POS[NLen];

int N;

inline void Down_Heap(int nod)
{
    int aux = HEAP[nod], L, R;

    while(L <= HEAP[0])
    {
        L = nod << 1;
        R = L + 1;

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

inline void Up_Heap(int nod)
{
    int aux = HEAP[nod];

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

    HEAP[nod] = aux;
    POS[aux] = nod;
}

inline void Pop_Heap(int nod)
{
    HEAP[nod] = HEAP[ HEAP[0] -- ];
    POS[ HEAP[nod] ] = nod;

    Down_Heap(POS[ HEAP[nod] ]);
}

inline void Push_Heap(int nod)
{
    HEAP[ ++ HEAP[0] ] = nod;
    POS[nod] = HEAP[0];
}

inline void dij(int nod)
{
    int USE[NLen];

    for(int i = 1; i <= N; ++ i)
    {
        DIST[i] = inf;
        HEAP[i] = 0;
        POS[i] = 0;
    }
    memset(USE, 0, sizeof(USE));

    DIST[nod] = 0;
    HEAP[0] = 1;
    HEAP[1] = 1;
    POS[1] = 1;
    USE[nod] = 1;

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

        for(int i = 0; i < G[nod].size(); ++ i)
            if(DIST[ G[nod][i].first ] == inf || DIST[ G[nod][i].first ] > DIST[nod] + G[nod][i].second)
            {
                DIST[ G[nod][i].first ] = DIST[nod] + G[nod][i].second;
                if( ! USE[ G[nod][i].first ])
                {
                    USE[ G[nod][i].first ] = 1;
                    Push_Heap(G[nod][i].first);
                }

                Up_Heap(POS[ G[nod][i].first ]);
            }
    }
}

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;
}