#include <fstream>
#include <vector>
#include <queue>

std::vector < std::vector < std::pair < int, int > > > g;
std::vector < int > d;
std::priority_queue < std::pair < int, int >, std::vector < std::pair < int, int > >, std::greater < std::pair <int, int> > > h;

int main( ) {
    std::ifstream fin("dijkstra.in");
    int n, m;
    fin >> n >> m;
    g.resize(n);
    for ( int i = 0; i < m; ++ i ) {
        int x, y, z;
        fin >> x >> y >> z;
        g[x-1].push_back(std::make_pair(z, y-1));
    }
    fin.close();

    d.resize(n, -1);
    d[0] = 0;
    h.push(std::make_pair(0, 0));
    while ( h.empty() == 0 ) {
        int x = h.top().second;
        int y = h.top().first;
        h.pop();
        if ( d[x] == y ) {
            for ( int i = 0; i < int(g[x].size()); ++ i ) {
                int xn = g[x][i].second;
                int yn = g[x][i].first;
                if ( d[xn] == -1 || d[xn] > d[x]+yn ) {
                    d[xn] = d[x]+yn;
                    h.push(std::make_pair(d[xn], xn));
                }
            }
        }
    }

    std::ofstream fout("dijkstra.out");
    for ( int i = 1; i < n; ++ i ) {
        if ( d[i] != -1 ) {
            fout << d[i] << " ";
        } else {
            fout << "0 ";
        }
    }
    fout << "\n";
    fout.close();
    return 0;
}