#include <bits/stdc++.h>

using namespace std;

const int N=5e4+5,INF=2e4+5;

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

struct graf
{
    vector <pair<int,int> > v; // nod & cost
    bool parcurs;
}la[N];

int sol[N];
int main()
{
    int n,m;
    in>>n>>m;

    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        in>>a>>b>>c;
        la[a].v.push_back(make_pair(b,c));
    }

    for(int i=2;i<=n;i++) sol[i]=INF;
    sol[1]=0;

    for(int l=1;l<=n;l++)
    {
        int next,nextVal=INF;
        for(int i=1;i<=n;i++)
            if(!la[i].parcurs && sol[i]<nextVal)
        {
            next=i;
            nextVal=sol[i];
        }

        la[next].parcurs=1;
        for(int i=0;i<la[next].v.size();i++)
            if(sol[next]+la[next].v[i].second < sol[la[next].v[i].first])
            sol[la[next].v[i].first]=sol[next]+la[next].v[i].second;
    }

    for(int i=2;i<=n;i++)
        out<<sol[i]<<' ';

    return 0;
}