#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define MAX (1<<28)
using namespace std;

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

vector<pair<int,int> >graph[50005];

int nr_entered[50005], n, m, from, to, dp[50005], cost;



struct nod{
    int ind, c;

    nod(int a, int b)
    {
        ind=a;
        c=b;
    }
};

bool operator<(nod a, nod b)
{
    return a.c>b.c;
}

priority_queue<nod>q;

void rezolvare()
{
    nod el=nod(1,0);
    q.push(el);
    while (!q.empty())
    {
        nod element=q.top();
        q.pop();
        for (auto &v:graph[element.ind])
        {
            dp[v.first]=min(dp[v.first],dp[element.ind]+v.second);
            nr_entered[v.first]--;
            if (nr_entered[v.first]==0)
            {
                nod adaug=nod(v.first,dp[v.first]);
                q.push(adaug);
            }
        }
    }
    for (int i=2; i<=n; i++)
    {
        g << dp[i] <<' ';
    }
}

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; i++)
    {
        f >> from >> to >> cost;
        nr_entered[to]++;
        graph[from].push_back(make_pair(to,cost));
    }
    for (int i=2; i<=n; i++)
    {
        dp[i]=MAX;
    }
    rezolvare();
    return 0;
}