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

#define inf 20001

using namespace std;

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

struct Nod
{
    int cost;
    int nr;
};

struct compare
{
    bool operator()(Nod &a, Nod &b)
    {
        return a.cost>b.cost;
    }
};

priority_queue <Nod, vector<Nod>, compare> q;
vector <Nod> M[50001];

int n, m, x, cate=0;
Nod aux, mnv;
int D[50001];
bool vf[50001];

int main()
{
    fin>>n>>m;
    for(int i=0; i<m; i++)
    {
        fin>>x>>aux.nr>>aux.cost;
        M[x].push_back(aux);
    }

    for(auto i: M[1])
    {
        q.push(i);
        D[i.nr]=i.cost;
        vf[i.nr]=1;
    }
    for(int i=2; i<=n; i++)
    {
        if(!vf[i])
        {
            aux.nr=i;
            aux.cost=inf;
            q.push(aux);
            D[i]=inf;
            vf[i]=1;
        }
    }

    while(!q.empty())
    {
        aux=q.top();
        if(aux.cost!=D[aux.nr])
        {
            q.pop();
        }
        else
        {
            for(auto i: M[aux.nr])
            {
                if(D[i.nr]>i.cost+aux.cost)
                {
                    D[i.nr]=i.cost+aux.cost;
                    mnv.nr=i.nr;
                    mnv.cost=D[i.nr];
                    q.push(mnv);
                }
            }
            q.pop();
        }
    }

    for(int i=2; i<=n; i++)
    {
        fout<<D[i]<<' ';
    }

    fin.close();
    fout.close();
    return 0;
}