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