#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <set>
#define INF 1000000010
#define NMAX 50010

using namespace std;

FILE *f = fopen("dijkstra.in", "r");
ofstream g ("dijkstra.out");

struct Pair
{
    int y, c;
};

vector< Pair > a[NMAX];
multiset< pair<int, int> > my_set;
int n, m, v[NMAX];

int main()
{
    fscanf(f, "%d%d", &n, &m);

    for (int c, x, y, i = 0; i < m; i++)
    {
        fscanf(f, "%d%d%d", &x, &y, &c);
        Pair p;
        p.y = y;
        p.c = c;
        a[x].push_back(p);
    }
    for (int i = 1; i <= n; i++)
        v[i] = INF;
    v[1] = 0;

    my_set.insert(make_pair(0, 1));
    while (!my_set.empty())
    {
        int node = my_set.begin()->second;
        int d = my_set.begin()->first;
        my_set.erase(my_set.begin());

        for (unsigned i = 0; i < a[node].size(); i++)
        {
            int to = a[node][i].y;
            int c = a[node][i].c;
            if (d + c < v[to])
            {
                if (v[to] < INF)
                    my_set.erase(my_set.find(make_pair(v[to], to)));
                v[to] = d + c;
                my_set.insert(make_pair(v[to], to));
            }
        }
    }

    for (int i = 2; i <= n; i++)
        if (v[i] != INF)
            g << v[i] << ' ';
        else
            g <<"0 ";
    return 0;
}