#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream si("dijkstra.in");
ofstream so("dijkstra.out");
const int NMAX=50005;

struct muchie
{
    int pct,c;
    bool operator <(const muchie &var) const
    {
        return c<var.c;
    }
};
vector<muchie> v[NMAX];
int d[NMAX];
priority_queue<muchie> x;
const int INF=1000000000;
int main()
{
    int n,m;
    si>>n>>m;
    int a,b,c,i;
    for(i=0;i<m;++i)
    {
        si>>a>>b>>c;
        v[a].push_back({b,c});
    }
    for(i=2;i<=n;++i)
        d[i]=INF;
    d[1]=0;
    x.push({1,0});
    int el;
    while(!x.empty())
    {
        a=x.top().pct;
        b=x.top().c;
        x.pop();
        if(d[a]!=b)
            continue;
        el=v[a].size();
        for(i=0;i<el;++i)
        {
            if(d[v[a][i].pct]>b+v[a][i].c)
            {
                d[v[a][i].pct]=b+v[a][i].c;
                x.push({v[a][i].pct,d[v[a][i].pct]});
            }
        }
    }
    for(i=2;i<=n;++i)
    {
        if(d[i]!=INF)
            so<<d[i]<<' ';
        else
            so<<0<<' ';
    }
    so<<'\n';
    return 0;
}