//doar ca conventie INF= o valoare la care costul nu poate ajunge
//daca un element nu are nimic cu cost c/d atunci el va trimite la el odata ce c/d>0
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define all(x) x.begin(),x.end()
#define pb push_back
struct muchie
{
    int to,cost;
};
const int inf=2e9;
struct node
{
    int minn;
    int poz;
    bool operator< (const node& b)const
    {
        if(minn==b.minn)
        {
            return poz<b.poz;
        }
        return minn<b.minn;
    }
};
class Aint
{
    int n;
    vector<node>aint;
    void modify(int poz)
    {
        for(poz>>=1;poz>0;poz>>=1)
        {
            aint[poz]=min( aint[poz<<1] , aint[poz<<1|1] );
        }
    }
public:
    void set(int poz,int val)
    {
        poz+=n;
        aint[poz].minn=val;
        modify(poz);
    }
    node query()
    {
        return aint[1];
    }
    Aint(int n)
    {
        this->n=n;
        aint.resize(2*n);
        for(int i=0;i<n;i++)
        {
            aint[n+i].poz=i;
        }
    }
};


main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    int n,m;
    cin>>n>>m;
    vector<vector<muchie>>g(n);
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        x--;
        y--;
        g[x].pb({y,z});
    }
    vector<int>rez(n,inf);
    rez[0]=0;
    Aint aint(n);
    for(int i=0;i<n;i++)
    {
        aint.set(i , rez[i]);
    }
    while( aint.query().minn < inf )
    {
        int then=aint.query().poz;
        for(auto &c:g[then])
        {
            if(rez[c.to] > rez[then]+ c.cost)
            {
                rez[c.to] = rez[then]+c.cost;
                aint.set(c.to , rez[c.to]);
            }
        }

        aint.set(then , inf);
    }
    for(int i=1;i<n;i++)
    {
        if(rez[i]!=inf)
        {
            cout<<rez[i]<<' ';
        }
        else
        {
            cout<<"0 ";
        }
    }
}