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

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

int poz[50001];

struct dist
{
    int d, ind, i;

    dist()
    {
        ind = 0;
    }

    bool operator<(const dist &a) const
    {
        return d > a.d;
    }

    dist operator=(dist a)
    {
        ind = a.ind;
        poz[ind] = i;
        d = a.d;
    }
} d[50001];

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

void dijkstra()
{
    bool ok = true;
    int N = n, nod = 1;
    d[1].d = 0;
    while (N)
    {
        nod = d[1].ind;
        int dist = d[1].d;
        if (dist == oo)
            break;
        for (int i = 0 ; i < adj[nod].size(); i++)
        {
            if (dist == oo && ok)
            {
                ok = false;
                cout << nod << '\n';

            }
            int next = adj[nod][i].first, c = adj[nod][i].second;
            if (dist + c < d[poz[next]].d)
            {
                d[poz[next]].d = dist + c;
                make_heap(d + 1, d + N + 1);
            }
        }
        pop_heap(d + 1, d + N + 1);
        N--;
    }
}

int main()
{
    int x, y, c;

    fin >> n >> m;
    while (m--)
    {
        fin >> x >> y >> c;
        adj[x].push_back(make_pair(y, c));
    }

    for (int i = 1; i <= n; i++)
    {
        poz[i] = i;
        d[i].ind = i;
        d[i].d = oo;
        d[i].i = i;
    }
    dijkstra();

    for (int i = 2; i <= n; i++)
    {
        if (d[poz[i]].d == oo)
            fout << "0 ";
        else
            fout << d[poz[i]].d << ' ';
    }
}