#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int viz[50010],d[50010],c,mini=1e9,i,j,n,m,x,y,s[50010];
struct ceva
{
    int nod,cost;
    bool operator < (const ceva &x) const
    {
        return cost>x.cost;
    }
}p,p1;
vector <ceva> v[50010];
priority_queue <ceva> pq;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back({y,c});
    }
    for(i=2;i<=n;i++)
        d[i]=1e9;
    d[1]=0;
    pq.push({1,0});
    while(!pq.empty())
    {
        p=pq.top();
        pq.pop();
        if(viz[p.nod]!=0)
            continue;
        viz[p.nod]=1;
        for(auto it:v[p.nod])
        {
            if(d[it.nod]>d[p.nod]+it.cost)
            {
                d[it.nod]=d[p.nod]+it.cost;
                pq.push({it.nod,d[it.nod]});
            }
        }
    }
    for(i=2;i<=n;i++)
        if(d[i]!=1e9)
            fout<<d[i]<<' ';
        else
            fout<<0<<' ';
    return 0;
}