#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin("djikstra.in");
ofstream fout("djikstra.out");
int d[50005];
bool sel[50005];
vector <pair<int,int>>g[50005];
priority_queue<pair<int,int>> h;
int n,m;
void dijkstra(int nodStart)
{
    int a,y,b,c,x;
    for(int i=1; i<=n; i++)
    {
        d[i]=20001;
    }
    d[nodStart]=0;
    h.push(make_pair(-d[nodStart],nodStart));
    while(!h.empty())
    {
        while(!h.empty()&&sel[h.top().second])
        {
            h.pop();
        }
        if(h.empty())
        {
            return;
        }
        x=h.top().second;
        sel[x]=true;
        for(auto p:g[x])
        {
            y=p.first;
            c=p.second;
            if(d[x]+c<d[y])
            {
                d[y]=d[x]+c;
                h.push(make_pair(-d[y],y));
            }
        }
    }
}

void print()
{
    for(int i = 2; i <= n; i++)
    {
        if(d[i] != 20001)
            fout << d[i] << " ";
        else
            fout << "0 ";
    }
}

int main()
{
    int i,a,b,c;
    fin>>n>>m;

    for(i=1; i<=n; i++)
    {
        fin>>a>>b>>c;
        g[a].push_back(make_pair(b,c));
    }
    dijkstra(1);
    print();
    return 0;
}