#include <fstream>
#define DIM 50001
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <set>
#define INF 0x3f3f3f3f

using namespace std;

int n, a, b, m, lungime, visited, d[DIM], vfc, part;

struct muchie
{
    int vf, l;
};

struct drum
{
    int dest, val;
};

struct classcomp
{
    bool operator () (const drum &A, const drum &B) const
    {
        if(A.val==B.val)
        {
            return A.dest<B.dest;
        }
        else return A.val<B.val;
    }
};

set <drum, classcomp> res;

set <drum, classcomp> :: iterator it;

drum temp1;

vector <muchie> nod[DIM];

muchie temp;

int main()
{
    ifstream in ("dijkstra.in");
    ofstream out ("dijkstra.out");
    in>>n>>m;
    while(m--)
        {
            in>>a>>b>>lungime;
            temp.vf=b;
            temp.l=lungime;
            nod[a].push_back(temp);
        }
    for(int i=2; i<=n; ++i)
    {
        temp1.dest=i;
        temp1.val=INF;
        res.insert(temp1);
        d[i]=INF;
    }
    temp1.val=0; temp1.dest=1;
    res.insert(temp1);
    while(res.begin()!=res.end()&&part!=INF)
    {
        it=res.begin();
        vfc=(*it).dest;
        part=(*it).val;
        res.erase(it);
        for(vector <muchie> ::iterator it1=nod[vfc].begin(); it1!=nod[vfc].end(); ++it1)
        {
            if(d[(*it1).vf]>part+(*it1).l)
            {
                temp1.dest=(*it1).vf;
                temp1.val=d[(*it1).vf];
                res.erase(temp1);
                d[(*it1).vf]=part+(*it1).l;
                temp1.val=d[(*it1).vf];
                res.insert(temp1);
            }
        }
    }
    for(int i=2; i<=n; ++i)
    {
        if(d[i]==INF)
            d[i]=0;
        out<<d[i]<<" ";
    }
    out<<"\n";
    in.close();
    out.close();
    return 0;
}