#include <bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector<pair<int,int>>mat[50005];
priority_queue<pair<int,int>>q;
int dist[50005];

void dijkstra(int nod, int n)
{
    dist[nod]=0;
    q.push({-dist[nod],nod}); //neg pt ca vreau minim, pe cand pq lucreaza pe maxime
    while(!q.empty())
    {
        int nodCrt=q.top().second; //iau prim nod+costul lui
        int d=-q.top().first;
        q.pop();
        if(d!=dist[nodCrt])
            continue;

        for(int i=0;i<mat[nodCrt].size(); i++)
        {
            if(dist[mat[nodCrt][i].first]>dist[nodCrt]+mat[nodCrt][i].second)
                dist[mat[nodCrt][i].first]=dist[nodCrt]+mat[nodCrt][i].second;
            q.push({-dist[mat[nodCrt][i].first], mat[nodCrt][i].first});
        }
    }
    for(int i=2;i<=n;i++){
        if(dist[i]==1e9)
            dist[i]=0;
        fout<<dist[i]<<" ";
}
}
int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        dist[i]=1e9;
    for(int i=1;i<=n;i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        mat[x].push_back({y,cost});
    }

    dijkstra(1,n);

    return 0;
}