#include <bits/stdc++.h>
#define infinit 2000000000
using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");
// 10   1 3 0 5 2 4 7 9 8 6

struct graf{
    int nod;
    int cost;
};

int n, p;
bool checked[50005];
vector <graf> graphs[50005];
graf heap[251000], dist[50005];

void up_heap(int k)
{
    while(k > 1)
    {
        if(heap[k>>1].cost > heap[k].cost)
            swap(heap[k>>1], heap[k]), k = (k>>1);
        else
            break;
    }
}

void blend_in_heap(int k, int heap_len)
{
    int len;
    while(k <= (heap_len>>1))
    {
        len = k<<1;
        if(heap[len + 1].cost < heap[len].cost)
        len++;
        if (heap[len].cost < heap[k].cost)
            swap(heap[len], heap[k]), k = len;
        else break;
    }
}

void heap_infinity(int k)
{
    int i;
    for(i = 1; i <= k; i++)
        heap[i].cost = infinit;
}
void construct_distance()
{
    int i;
    for(i = 1; i <= n; i++)
        dist[i].cost = infinit, dist[i].nod = i;
}

void dijkstra(int nod_start)
{
    int heap_len = 0, k, var;
    unsigned i, len;
    dist[nod_start].cost = 0;
    checked[nod_start] = 1;
    len = graphs[nod_start].size();
    for(i = 0; i < len; i++)
    {
        var = graphs[nod_start][i].nod;
        if(graphs[nod_start][i].cost < dist[var].cost)
        {
        heap_len++;
        dist[graphs[nod_start][i].nod].cost = graphs[nod_start][i].cost;
        heap[heap_len] = dist[graphs[nod_start][i].nod];
        up_heap(heap_len);
        }
    }
    while(heap_len > 0)
    {
        k = heap[1].nod;
        checked[k] = 1;
        len = graphs[k].size();
        for(i = 0; i < len; i++)
        {
            var = graphs[k][i].nod;
            if(!checked[var])
            {
                if(dist[k].cost + graphs[k][i].cost < dist[var].cost)
                {
                    dist[var].cost = dist[k].cost + graphs[k][i].cost, heap_len++;
                    heap[heap_len] = dist[graphs[k][i].nod];
                    up_heap(heap_len);
                }
            }
        }
        heap[1] = heap[heap_len];
        blend_in_heap(1, heap_len);
        heap_len--;
    }
}

int main()
{
    int x, ct = 0;
    graf var;
    fin >> n >> p;
    while(fin >> x >> var.nod >> var.cost)
        graphs[x].push_back(var), ct++;
    heap_infinity(ct + 40);
    construct_distance();
    dijkstra(1);
    for(int i = 1; i <= n; i++)
    {
        if(dist[i].cost == infinit)
        fout << 0 << " ";
        else if (dist[i].cost != 0)
        fout << dist[i].cost << " ";
    }

    return 0;
}

   /* for(i = 1; i <= n; i++)
    {
        fout << i << " : ";
        for(j = 0; j < graphs[i].size(); j++)
            fout << graphs[i][j].nod << " si " << graphs[i][j].cost << " ";
        fout << endl;
    }
    */