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