#include <fstream>
#include <vector>
#include <iostream>

using std::vector;
using std::endl;
using std::cout;

const int INF = 0x3f3f3f;

struct muchie
{
    int nod1;
    int nod2;
    int dist;
};

int main()
{
    std::ifstream in("dijkstra.in");
    std::ofstream out("dijkstra.out");
    int N,M;
    in >> N >> M;
    ++N;
    vector<muchie> a;
    for (int i = 0; i < M; ++i)
    {
        muchie temp;
        in >> temp.nod1 >> temp.nod2 >> temp.dist;
        a.push_back(temp);
    }

    int DIST[N],PRED[N];
    DIST[1] = 0; PRED[1] = 0;
    for (int i = 2; i < N; ++i)
        DIST[i] = PRED[i] = INF;

    for (int i = 1; i < N; ++i)
        for (int j = 0; j < a.size(); ++j)
    if ( DIST[ a[j].nod1 ] + a[j].dist < DIST[ a[j].nod2 ] ) {
             DIST[ a[j].nod2 ] = DIST[ a[j].nod1 ] + a[j].dist;
             PRED[ a[j].nod2 ] = a[j].nod1;
    }

    for (int i = 2; i < N; ++i)
        out << DIST[i] << " ";
    return 0;
}