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

using namespace std;
FILE* f, * g;

class compar
{
public:
    bool operator() (pair <int, int> X, pair <int, int> Y)
    {
        return (X.second > Y.second);
    }
};

priority_queue <pair <int, int>, vector <pair <int, int> >, compar> q;//imi introduce in coada nodurlle sortate crescator in functie de cost
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 drum[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)
        drum[i] = 2000000000;
    q.push({ 1,0 });
    while (!q.empty())
    {
        //in q.top().first e nodul si in q.top().second e costul
        no = q.top().first;
        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;
                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,dist });
                }
            }
        }
        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;
}