#include <cstdio>
#include <vector>
#include <queue>
#define lim 60000
#define oo ((1<<30)-1)
using namespace std;


int n,m;
FILE *outFile = fopen("dijkstra.out","w");

struct nod
{
    int v;
    int cst;
}Nod;
vector<nod> graph[lim];


int cost[lim];
int viz [lim];

struct cmp
{
    bool operator()(int a,int b)
    {
        return cost[a] > cost[b];
    }
};
priority_queue<int, vector<int>, cmp> Q;

void citire()
{
    freopen("dijkstra.in","r",stdin);
    scanf("%d %d",&n,&m);

    for(int i =0 ; i <  n; i++)
    {
        int x;
        scanf("%d %d %d",&x,&Nod.v,&Nod.cst);
        graph[x].push_back(Nod);
    }
}

void dijkstra(int start){

    for(int i = 2 ; i <= n; cost[i] = oo, i++);
    Q.push(start);
    viz[start] = 1;
    while(!Q.empty())
    {
        int min = Q.top();
        Q.pop();

        for(int i = 0 ; i < graph[min].size();i++)
        {
            if(!viz[graph[min][i].v])
            {
                int sum = cost[min] + graph[min][i].cst;
                if(sum < cost[graph[min][i].v])
                {
                    cost[graph[min][i].v] = sum;
                    Q.push(graph[min][i].v);
                }
            }
        }
    }



}

int main()
{

    citire();
    dijkstra(1);
    for(int i = 2; i <= n; i++)
    {
        fprintf(outFile,"%d ", cost[i]);
    }
    return 0;
}