#include <bits/stdc++.h>
#define NMAX 50003
#define INF 18446744073709551610
#define pi pair<unsigned long long, int>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,x,y,c;
struct nod{
    vector<pi> adj;
};
vector<nod> v;
priority_queue<pi, vector<pi>, greater<pi> > pq;
//dijkstra optim(adica blana)
void dijkstra(int root)
{
    unsigned long long baczaur[NMAX],w,nod,e;
    for (int i=2;i<=n;i++)
    {
        baczaur[i]=INF;
    }
    baczaur[root]=0;
    pq.push(make_pair(0,root));
    while(!pq.empty())
    {
        nod = pq.top().second;
        pq.pop();
        for (unsigned int i=0;i<v[nod].adj.size();i++)
        {
            w=v[nod].adj[i].first;
            e=v[nod].adj[i].second;
            if (baczaur[e]>baczaur[nod]+w)
            {
                baczaur[e]=baczaur[nod]+w;
                pq.push(make_pair(baczaur[e],e));
            }
        }
    }
    for (int i=2;i<=n;i++)
    {
        g<<baczaur[i]<<" ";
    }
}
int main()
{
    f>>n>>m;
    v.resize(n+2);
    for (int i=0;i<m;i++)
    {
        f>>x>>y>>c;
        v[x].adj.push_back(make_pair(c,y));
    }
    dijkstra(1);
    return 0;
}