#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];
bool OK[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;

    OK[1] = 1;

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

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

        OK[vf_min] = 1;

        for (auto i = 0; i < A[vf_min].size(); i++)
            if (!OK[A[vf_min][i].first] && drum[A[vf_min][i].first] > dmin + A[vf_min][i].second)
                drum[A[vf_min][i].first] = dmin + A[vf_min][i].second;
    }

    for (int i = 2; i <= n; i++)
    {
        if (drum[i] == inf)
            out << 0;
        else
            out << drum[i] <<' ';
    }

    return 0;
}