#include <fstream>
#include <climits>
#include <vector>
#include <queue>

using namespace std;

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

const int nmax = 50005;
const int inf = INT_MAX;
int fr[nmax], n, m, cost[nmax];
vector< pair<int, int> > a[nmax];
priority_queue< pair<int, int> > Q;

int findMin()
{
    while(!Q.empty() && fr[Q.top().second])
        Q.pop();

    if(Q.empty())
        return -1;

    int nod = Q.top().second;
    Q.pop();
    return nod;
}

void Dij()
{
    for(int i = 2; i <= n; i ++)
        cost[i] = inf;
    Q.push({0, 1});
    for(int i = 1; i <= n; i ++)
    {
        int nod = findMin();
        if(nod == -1)
            return;

        fr[nod] = 1;
        while(a[nod].size())
        {
            pair<int, int> k = a[nod].back();
            a[nod].pop_back();
            if(cost[k.first] > k.second + cost[nod])
            {
                cost[k.first] = k.second + cost[nod];
                Q.push({-cost[k.first], k.first});
            }
        }
    }
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int x, y, c;
        f >> x >> y >> c;
        a[x].push_back({y, c});
    }

    for(int i = 2; i <= n; i ++)
        cost[i] = inf;

    Dij();

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

        else
            g << cost[i] << " ";
    return 0;
}