#include <bits/stdc++.h>

using namespace std;
int n,m;
const int INF=INT_MAX;
vector<pair<int,int>>vecini[50001];
vector<int>d;
vector<bool>viz;
struct cmp
{
    bool operator()(int a, int b)
    {
        return d[a]>d[b];
    }
};
priority_queue<int,vector<int>,cmp> pq;
void dijkstra(int nod)
{
    viz[nod]=true;
    d[nod]=0;
    pq.push(nod);
    while(!pq.empty())
    {
        int x=pq.top();
        pq.pop();
        viz[x]=false;
        for(auto vecin:vecini[x])
        {
            int cost=vecin.second;
            int v=vecin.first;
            if(d[v]>d[x]+cost)
            {
                d[v]=d[x]+cost;
                if(!viz[v])
                {
                    pq.push(v);
                    viz[v]=true;
                }
            }
        }
    }
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    viz=vector<bool>(n+1,false);
    d=vector<int>(n+1,INF);
    for(int i=1; i<=m; i++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        vecini[a].push_back(make_pair(b,c));
    }
    dijkstra(1);
    for(int i=2;i<=n;i++)
        if(d[i]==INF)
        d[i]=0;
    for(int i=2;i<=n;i++)
        cout<<d[i]<<" ";
    return 0;
}