#include <fstream>
#include <vector>


using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int nMAX = 50000;
const int mMAX = 250000;
const int INFINIT = 1<<30;

struct muchie {
    int u, v, c;
};

int n, m, dist[nMAX];
vector <vector<muchie>> lista_vecini(nMAX);


void dijkstra(int nod)
{
    vector <int> Q;

     for (int i = 1; i <= n; i++)
    {
        dist[i] = INFINIT;//pt fiecare nod de la 1 la n, initializam distanta cu infinit cf wikipedia, desi as fi facut de la 2 incolo
        Q.push_back(i);// toate nodurile in coada
    }

    for (int i = 0; i < lista_vecini[nod].size(); i++)
    {
        dist[lista_vecini[nod][i].v] = lista_vecini[nod][i].c;
        Q.push_back(lista_vecini[nod][i].v);
    }
    dist[nod] = 0;
    
    while (!Q.empty())
    {
        int index = 0;
        for (int i = 1; i < Q.size(); i++)   //determin index varf din Q cu dist minima cf wikipedia https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
            if (dist[Q[index]] > dist[Q[i]])
                index = i; //iau alt u, ca are distanta gasita mai mica
        int nodnou = Q[index];
        Q.erase(Q.begin() + index);   //scot din coada respectivul element

        for (int i = 0; i < lista_vecini[nodnou].size(); i++) // pt fiecare vecin v al noului u ramas in Q
        {
            if ( (dist[lista_vecini[nodnou][i].u] + lista_vecini[nodnou][i].c) < dist[lista_vecini[nodnou][i].v])
                dist[lista_vecini[nodnou][i].v] = dist[lista_vecini[nodnou][i].u] + lista_vecini[nodnou][i].c;
        }
    }

    for (int i = 2; i <= n; i++)
        if (dist[i] == INFINIT)
            g << 0 << " ";
        else
            g << dist[i] << " ";
    f.close();
    g.close();
}

void citire_muchii(int m) {
    int u, v, c;
    for (int i = 0; i < m; i++) {
        f >> u >> v >> c;
        muchie muc;
        muc.u = u; muc.v = v; muc.c = c;
        lista_vecini[u].push_back(muc);
    }
}

int main()
{
    f >> n >> m; 
    citire_muchii(m);
    dijkstra(1);
return 0;
}