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

#define NLen 0x10000
#define inf 0x7fffffff

using namespace std;

ifstream fi;
ofstream fo;

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

int DIST[NLen];
int N;

inline bool cmp(const int & a, const int & b)
{
    return DIST[a] > DIST[b];
}

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

    for(int i = 1; i <= N; ++ i) DIST[i] = inf;

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

    while(HEAP[0])
    {
        nod = HEAP[1];
        pop_heap(HEAP + 1, HEAP + HEAP[0] + 1, cmp);

        HEAP[0] -- ;

        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;

                HEAP[ ++ HEAP[0] ] = G[nod][i].first;
                push_heap(HEAP + 1, HEAP + HEAP[0] + 1, cmp);
            }
    }
}

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