#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax = 50005;
const int inf = (1<<29);
vector <pair <int,int> > g[nmax];
int heap[nmax], poz[nmax], dist[nmax], n, dim;

void Swap(int i, int j)
{
    swap(heap[i], heap[j]);
    poz[heap[i]]=i;
    poz[heap[j]]=j;
}

int ord(int i, int j)
{
    return dist[heap[i]] < dist[heap[j]];
}

void heap_pop(int dad)
{
    int son=(dad<<1);
    if(son>dim) return;
    if(son<dim && ord(son+1, son)) son++;
    if(ord(son, dad))
    {
        Swap(son, dad);
        heap_pop(son);
    }
}

void heap_push(int son)
{
    int dad=(son>>1);
    if(!son) return;
    if(ord(son, dad))
    {
        Swap(son, dad);
        heap_push(dad);
    }
}

void dijkstra()
{
    int i, dad, son, cost;
    for(i=1; i<=n; i++)
    {
        dist[i]=(1<<29);
        heap[i]=poz[i]=i;
    }
    dist[1]=0;
    dim=n;
    while(dim && dist[heap[1]]<inf)
    {
        dad=heap[1];
        Swap(1, dim);
        dim--;
        heap_pop(1);
        for(i=0; i<g[dad].size(); i++)
        {
            son=g[dad][i].first;
            cost=g[dad][i].second;
            if(dist[son] > dist[dad]+cost)
            {
                dist[son]=dist[dad]+cost;
                heap_push(son);
            }
        }
    }
}

int main()
{
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
    int i, m, x, y, c;
    fin >> n >> m;
    for(i=1; i<=n; i++)
    {
        fin >> x >> y >> c;
        g[x].push_back(make_pair(y, c));
    }
    dijkstra();
    for(i=2; i<=n; i++)
    {
        if(dist[i]==inf) fout << 0 << " ";
        else fout << dist[i] << " ";
    }
    fin.close();
    fout.close();
    return 0;
}