#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
struct muchie
{
    int fiu;
    int cost;
};
struct CompareCost
{
    bool operator()(muchie const & muc1, muchie const &muc2)
    {
        return muc1.cost > muc2.cost;
    }
};
int main()
{
    int n, m;
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    f >> n >> m;

    vector<vector<muchie>> lista_adiacenta(n+1);
    int a, b, c;
    for(int i = 0; i < m; i++)
    {
        f >> a >> b >> c;
        muchie muc;
        muc.fiu = b;
        muc.cost = c;
        lista_adiacenta[a].push_back(muc);
    }

    int distante_apm[n + 1];
    int tati[n + 1];
    bool vizitat[n+1];
    for(int i = 0; i <= n; i++)
    {
        distante_apm[i] = INT_MAX;
        tati[i] = 0;
        vizitat[i] = false;
    }

    priority_queue<muchie, vector<muchie>, CompareCost> coada;

    muchie muc;
    muc.cost = 0;
    muc.fiu = 1;
    coada.push(muc);
    distante_apm[1] = 0;

    while(coada.empty() == false)
    {
        muchie minim = coada.top();
        coada.pop();
        if(vizitat[minim.fiu] == true)
            continue;

        vizitat[minim.fiu] = true;
            for(int j = 0; j < lista_adiacenta[minim.fiu].size(); j++)
            {
                muc = lista_adiacenta[minim.fiu][j];
                if(distante_apm[muc.fiu] > muc.cost + distante_apm[minim.fiu])
                {
                    distante_apm[muc.fiu] = muc.cost + distante_apm[minim.fiu];
                    tati[muc.fiu] = minim.fiu;
                    coada.push(muc);
                }
            }
    }

    for(int i = 2; i <= n; i++)
    {
        if(distante_apm[i] != INT_MAX)
            g << distante_apm[i] << " ";
            else
                g << 0 << " ";
    }

    return 0;
}