#include <bitset>
#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;
FILE* f, * g;

int drum[50002];
class compar//imi introduce in coada nodurlle sortate crescator in functie de cost
{
public:
    bool operator() (int X, int Y)
    {
        return (drum[X] > drum[Y]);
    }
};

priority_queue <int, vector <int>, compar> q;
vector <pair <int, int> > nod[50002];//asta e ca o matrice dinamica care memoreaza pe fiecare pozitie cate o ^structura^
//pair <int,int> e ca un fel de structura
bool viz[50002];

int main()
{
    int m, n, i, j, x, y, c, no, dist, cost, vecin;
    f = fopen("dijkstra.in", "r");
    g = fopen("dijkstra.out", "w");
    fscanf(f, "%d %d", &n, &m);
    for (i = 1;i <= m;++i)
    {
        fscanf(f, "%d %d %d", &x, &y, &c);
        nod[x].push_back({ y,c });//la fiecare nod introducem vecinii si costul fiecarui drum
    }
    for (i = 2;i <= n;++i)//eu am nevoie de drumul de cost cel mai mic posibil
        drum[i] = 2000000000;
    q.push(1);
    while (!q.empty())
    {
        no = q.top();//primul element din coada
        q.pop();
        if (!viz[no])//nu am mai trecut prin nodul acesta
        {
            for (i = 0;i < nod[no].size();++i)
            {
                vecin = nod[no][i].first;//vecinul nodului no
                cost = nod[no][i].second;//costul dintre nodul no si nodul i
                dist = drum[no] + cost;//costul pana la nodul no
                if (dist < drum[vecin])
                {
                    drum[vecin] = dist;
                    q.push({ vecin });
                }
            }
        }
        viz[no] = 1;
    }
    for (i = 2;i <= n;++i)
    {
        if (drum[i] == 2000000000)
            fprintf(g, "0 ");
        else
            fprintf(g, "%d ", drum[i]);
    }
    fclose(f);
    fclose(g);
    return 0;
}