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

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define NMAX 50005
#define inf 1e9

vector <pair<int,int > >graf[NMAX];
priority_queue<pair<int, int> > q;
int n, m, d[NMAX], viz[NMAX],ct;

void citire()
{
    f>>n>>m;
    for(int i = 0; i < m; i ++)
    {
        int a,b,c;
        f>>a>>b>>c;
        graf[a].push_back({b,c});
    }
}

void dijkstra()
{
    for(int i = 2; i <= n; i ++)
    {
        d[i] = inf;
        q.push({-inf, i});
    }
    d[1] = 0;
    q.push({0,1});
    while(!q.empty())
    {
        pair<int,int> best = q.top();
        q.pop();
        int nod = best.second;

        if(!viz[nod])
        {
            viz[nod] = 1;
            for(auto x :graf[nod])
            {
                int vecin = x.first;
                int c = x.second;
                if(d[nod] + c < d[vecin])
                {
                    d[vecin] = d[nod] + c;
                    q.push({-d[vecin],vecin});
                }
            }
        }


    }


}
void afisare()
{
    for(int i = 2; i <= n; i ++)
        if(d[i] == inf)
            g<<'0'<<" ";
        else g<<d[i]<<" ";
}
int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}