#include <fstream>
#include <vector>
#define inf 1000000005

using namespace std;

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

const int Nmax = 50005;

int n, m, x, y, lungime, vf_min, dmin;

int drum[Nmax], select[Nmax];
vector <pair <int, int>> A[Nmax];


int main()
{
    in >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        in >> x >> y >> lungime;
        A[x].push_back(make_pair(y, lungime));
    }

    for (auto i = 0; i < A[1].size(); i++)
        drum[A[1][i].first] = A[1][i].second;

    for (int i = 2; i <= n; i++)
        if (drum[i] == 0)
            drum[i] = inf;

    select[1] = 1;

    for (int j = 1; j < n; j++)
    {
        dmin = inf;

        for (int i = 1; i <= n; i++)
            if (!select[i] && drum[i] < dmin)
            {
                dmin = drum[i];
                vf_min = i;
            }

        select[vf_min] = 1;

        for (auto i = 0; i < A[vf_min].size(); i++)
        {
            int nod = A[vf_min][i].first;
            int val = A[vf_min][i].second;

            if (!select[nod] && drum[nod] > dmin + val)
                drum[nod] = dmin + val;
        }
    }

    for (int i = 2; i <= n; i++)
        out << drum[i] <<' ';

    return 0;
}