#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define oo (1 << 30)
#define NMax 50006

using namespace std;

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

struct Pereche{
    int costDrum;
    int nod;

    bool operator < (const Pereche &e) const
    {
        return costDrum > e.costDrum;
    }
};

priority_queue <Pereche> Q;
vector <pair <int, int> > L[NMax];
int n, m; ///n - numar noduri, m - numar muchie
int drum[NMax];

void Read ()
{
    int x, y, cost;
    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        L[x].push_back ({y, cost});
    }
}

void InitializareVectorDrumuri ()
{
    for (int i = 1; i <= n; i++)
    {
        drum[i] = oo;
    }
}

void Dijkstra ()
{
    int nodCurent, nodAdiacent, cost;

    drum[1] = 0;
    Q.push ({0, 1});

    while (!Q.empty ())
    {
        nodCurent = Q.top ().nod;
        Q.pop ();
        for (auto element : L[nodCurent])
        {
            nodAdiacent = element.first;
            cost = element.second;

            if (drum[nodAdiacent] > drum[nodCurent] + cost)
            {
                drum[nodAdiacent] = drum[nodCurent] + cost;
                Q.push ({drum[nodAdiacent], nodAdiacent});
            }
        }
    }
}

void Out ()
{
    for (int i = 2; i <= n; i++)
        if (drum[i] == oo)
            fout << "0 ";
        else
            fout << drum[i] << " ";
    fout << "\n";

}
int main()
{
    Read ();
    InitializareVectorDrumuri ();
    Dijkstra ();
    Out ();
    return 0;
}