#include <bits/stdc++.h>
#define infinit 7000000001

using namespace std;

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

priority_queue <pair<int,int>,vector <pair<int,int>>,greater <pair<int,int>>> q;

struct muchie
{
    int nod,cost;
};

vector <muchie> a[10001];
int viz[10001],n,d[10001];

void dijkstra(int s)
{
    int nod,cost,i,k,pmin;
    viz[s]=1;
    for(i=0;i<=n;i++)
    {
        d[i]=infinit;
    }
    d[s]=0;
    for(i=0;i<a[s].size();i++)
    {
        nod=a[s][i].nod;
        cost=a[s][i].cost;
        q.push({cost,nod});
        d[nod]=cost;
    }
    while(!q.empty())
    {
        pmin=q.top().second;
        q.pop();
        for(i=0;i<a[pmin].size();i++)
        {
            nod=a[pmin][i].nod;
            cost=a[pmin][i].cost;
            if(d[nod]>d[pmin]+cost)
            {
                d[nod]=d[pmin]+cost;
                q.push({d[nod],nod});
            }
        }
    }
}

int main()
{int m,i,nod,nod2,cost;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f>>nod>>nod2>>cost;
        a[nod].push_back({nod2,cost});
    }
    dijkstra(1);
    for(i=2;i<=n;i++)
    {
        if(d[i]==infinit)
        {
            d[i]=0;
        }
        g<<d[i]<<" ";
    }
    return 0;
}