#include <cstdio>
#include <vector>
#include <algorithm>
#define oo 0x7fffffff
using namespace std;

int dist[50001];

struct distante
{
    int i;
    bool operator<(const distante &a) const
    {
        return dist[i] < dist[a.i];
    }
} h[50001];

int n, m, len;
vector<pair<int, int> > adj[50001];
bool in[50001];

void dijkstra()
{
    for (int i = 2; i <= n; i++)
        dist[i] = oo;
    in[1] = 1;
    dist[1] = 0;
    h[0].i = 1;
    len = 1;
    while (len)
    {
        int nod = h[0].i, d = dist[nod];

        pop_heap(h, h + len);
        len--;

        for (int i = 0; i < adj[nod].size(); i++)
        {

            int next = adj[nod][i].first, c = d + adj[nod][i].second;
            if (c < dist[next])
            {
                if (!in[next])
                {
                    in[next] = 1;
                    h[len++].i = next;
                }
                dist[next] = c;
            }
        }

        if (len)
            make_heap(h, h + len);
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    setbuf(stdout, NULL);//sterge asta

    int x, y, c;

    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &x, &y, &c);
        adj[x].push_back(make_pair(y, c));
    }

    dijkstra();
    for (int i = 2; i <= n; i++)
        if (dist[i] != oo)
            printf("%d ", dist[i]);
        else
            printf("0 ");
}