#include <fstream>
#include <set>
#include <vector>
#include <queue>

using namespace std;

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

struct nod
{
    vector <pair<int, int>> vec;
};
nod v[50005];
int d[50005];
priority_queue <pair<int, int>> s;
int n, m;

int main()
{

    int INF = (1 << 30) - 1;

    f>>n>>m;
    int st, dr, c;
    for(int i = 1; i<=m; i++)
    {
        f>>st>>dr>>c;
        v[st].vec.push_back({dr, c});
    }

    for(int i = 2; i<=n; i++)
    {
        d[i] = INF;
    }
    s.push({-0, -1});
    /*for(int i = 0; i<v[1].vec.size(); i++)
    {
        d[v[1].vec[i].first] = v[1].vec[i].second;
        s.insert({v[1].vec[i].second, v[1].vec[i].first});
    }*/

    int dist, nd;
    while(!s.empty())
    {
        dist = -(s.top()).first;
        nd = -(s.top()).second;
        s.pop();

        for(int i = 0; i<v[nd].vec.size(); i++)
        {
            int to = v[nd].vec[i].first;
            int cost = v[nd].vec[i].second;
            if(d[to] > d[nd] + cost)
            {
                /*if(d[to] != INF)
                {
                    s.erase(s.find({d[to], to}));
                }*/

                d[to] = cost + d[nd];
                s.push({-d[to], -to});
            }
        }
    }

    for(int i = 2; i<=n; i++)
    {
        if(d[i] == INF)
        {
            g<<0<<" ";
        }
        else
        {
            g<<d[i]<<" ";
        }
    }


    return 0;
}