#include <fstream>

#include <vector>

#include <set>

using namespace std;



ifstream fin("dijkstra.in");

ofstream fout("dijkstra.out");



vector <pair <int, int>> v[50001];



long long d[50001];



struct el

{

    int nod;

    bool operator <(const el &alt) const

    {

        if (d[nod] == d[alt.nod])
            return nod < alt.nod;
        return d[nod] < d[alt.nod];

    }

};



multiset <el> s;



int main()

{

    int n, m, i, j, x, y, z;

    fin >> n >> m;

    for (i = 1; i<=m; i++)

    {

        fin >> x >> y >> z;

        v[x].push_back({y, z});

    }

    for (i = 1; i<=n; i++)

        d[i] = 1ll<<50;

    d[1] = 0;

    s.insert({1});

    for (i = 1; s.empty() == 0 && i<n; i++)

    {



        x = s.begin()->nod;

        s.erase(s.begin());



        for (j = 0; j<v[x].size(); j++)

            if (d[v[x][j].first] > d[x] + v[x][j].second)

            {

                if (d[v[x][j].first] < (1ll<<50))

                s.erase(s.find({v[x][j].first}));

                d[v[x][j].first] = d[x] + v[x][j].second;

                s.insert({v[x][j].first});

            }

    }

    for (i = 2; i<=n; i++)

    {

        if (d[i] < (1ll<<50))

            fout << d[i] << ' ';

        else

            fout << "0 ";

    }

    return 0;

}