#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 5e4;
const int INF = 1 << 30;

struct arc
{
    int varful, costul;
};

vector <arc> succesori[NMAX + 1];
int distante[NMAX + 1], heap[NMAX + 1], poz[NMAX + 1], n, m, nr_heap;

void schimb(int pozitia_1, int pozitia_2)
{
    swap(heap[pozitia_1], heap[pozitia_2]);
    poz[heap[pozitia_1]] = pozitia_1;
    poz[heap[pozitia_2]] = pozitia_2;
}

void urca(int heap[], int pozitie)
{
    while(pozitie > 1 && distante[heap[pozitie]] < distante[heap[pozitie /2]])
    {
        schimb(pozitie, pozitie / 2);
        pozitie /= 2;
    }
}

void adauga(int heap[], int &numarul_heap, int val)
{
    heap[++numarul_heap] = val;
    poz[val] = numarul_heap;
    urca(heap, numarul_heap);
}

void coboara(int heap[], int numarul_heap, int pozitie)
{
    int fiu_stang = 2*pozitie, fiu_dreapta = 2*pozitie + 1, bun = pozitie;
    if(fiu_stang <= numarul_heap && distante[heap[fiu_stang]] < distante[heap[bun]])
    {
        bun = fiu_stang;
    }
    if(fiu_dreapta <= numarul_heap && distante[heap[fiu_dreapta]] < distante[heap[bun]])
    {
        bun = fiu_dreapta;
    }
    if(bun != pozitie)
    {
        schimb(pozitie, bun);
        coboara(heap, numarul_heap, bun);
    }
}

void sterge(int heap[], int &numarul_heap, int pozitie)
{
    if(pozitie == numarul_heap)
    {
        numarul_heap--;
    }
    else
    {
        schimb(pozitie, numarul_heap--);
        urca(heap, pozitie);
        coboara(heap, numarul_heap, pozitie);
    }
}

void dijkstra (int pozitia_initiala)
{
    ///initializarea distantelor
    for(int i = 1; i <= n; i++)
    {
        distante[i] = INF;
    }
    distante[pozitia_initiala] = 0;

    adauga(heap, nr_heap, pozitia_initiala);
    while(nr_heap > 0)
    {
        int x = heap[1];
        sterge(heap, nr_heap, 1);
        for(auto a : succesori[x])
        {
            int y = a.varful;
            int c = a.costul;
            if(distante[x] + c < distante[y])
            {
                distante[y] = distante[x] + c;
                if(poz[y] == 0)
                {
                    adauga(heap, nr_heap, y);
                }
                else
                {
                    urca(heap, poz[y]);
                }
            }
        }
    }
}

int main()
{
    in >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int x, y, cost;
        in >> x >> y >> cost;
        succesori[x].push_back((arc){y, cost});
    }

    dijkstra(1);

    for(int i = 2; i <= n; i++)
    {
        if(distante[i] == INF)
        {
            distante[i] = 0;
        }
        out << distante[i] << " ";
    }

    in.close();
    out.close();
    return 0;
}