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

using namespace std;

ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");

const int MAXN = 50010;
const int INF = 0x3f3f3f3f;

int N;
vector < pair <int, int> > Graf[MAXN];
int Best[MAXN];

struct comp
{
    inline bool operator () (const int &A, const int &B) const
    {
        return Best[A] > Best[B];
    }
};

priority_queue <int, vector <int>, comp> Q;

int main()
{
    int N, M, a, b, c, i;
    int now;
    vector < pair <int, int> > :: iterator it;

    in >> N >> M;
    for (i = 1; i <= M; i ++){
        in >> a >> b >> c;

        Graf[a].push_back (make_pair (b, c));
    }

    for (i = 2; i <= N; i ++)
        Best[i] = INF;

    Q.push (1);

    while (!Q.empty ()){
        now  = Q.top ();
        Q.pop ();

        for (it = Graf[now].begin (); it != Graf[now].end (); ++ it)
            if (Best[now] + (it -> second) < Best[it -> first]){
                Best[it -> first] = Best[now] + (it -> second);
                Q.push (it -> first);
            }
    }

    for (i = 2; i <= N; i ++)
        if (Best[i] == INF)
            out << 0 << " ";
        else
            out << Best[i] << " ";

    return 0;
}