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

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct edge
{
    int s,n,w;
};

int N,M;
vector<edge> a;
vector<int> dist,prec;


int main()
{
    in >> N >> M;
    for (int i = 0; i < M; ++i)
    {
        edge t;
        in >> t.s >> t.n >> t.w;
        a.push_back(t);
    }
    dist.resize(N+1,2e9); prec.resize(N);
    dist[1] = 0;
    bool gandalf = 1;
    while (gandalf)
    {
        gandalf = 0;
        for (int i = 0; i < a.size(); ++i)
            if ( dist[ a[i].s ] + a[i].w < dist[ a[i].n ] ) {
                dist[ a[i].n ]= dist[ a[i].s ] + a[i].w;
                gandalf = 1;
                prec[ a[i].n ] = a[i].s;
            }
    }
    for (int i = 2; i < dist.size(); ++i)
        out << dist[i] << " ";
    return 0;
}