#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

#define NMAX 50005
#define oo 2000000000

using namespace std;

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

int N, M;
int d[NMAX+1];

void getGraph(vector <pair<int,int>> lad[NMAX])
{
    fin >> N >> M;
    int x, y, c;
    while (fin >> x >> y >> c)
    {
        lad[x].emplace_back(c,y);
    }
}
struct compara
{
    bool operator() (int x, int y)
    {
        return d[x] > d[y];
    }
};
void Dijkstra(vector <pair<int, int>> lad[NMAX], int startNode)
{
    //priority_queue de perechi cu semnificatia first = cost, second = nod
    //=> in varf va tine mereu nodul de cost minim => poate fi gasit in timp constant
    priority_queue < int, vector<int>, compara > coada;

    for (int i = 1; i < N + 1; i++)
        d[i] = oo;
    //vectorul de vizite 
    vector<bool> viz(N+1, false);
    d[startNode] = 0;
    coada.push(startNode);

    while (!coada.empty())
    {
        int nod_curent = coada.top();
    
        coada.pop();
        viz[nod_curent] = true;
        //for (vector<pair<int, int>>::iterator it = lad[nod_curent].begin(); it != lad[nod_curent].end(); it++)
        for(auto it : lad[nod_curent])
        {
            
            int vecin_curent = (it).second;
            int cost_catre_vecin = (it).first;

            int dist_curenta = d[nod_curent] + cost_catre_vecin;
            if (!viz[vecin_curent] && d[vecin_curent] > dist_curenta)
            {
                d[vecin_curent] = dist_curenta;
                coada.push(vecin_curent);
            }
        }
    }
    for (auto i = 2; i <= N; i++)
    {
        if (d[i] != oo) fout << d[i] << ' ';
        else fout << 0 << ' ';
    }
}

int main()
{
    vector <pair<int, int>> lad[NMAX];
    getGraph(lad);
    Dijkstra(lad, 1);
}