#include <bits/stdc++.h>
#define INF 1e9
#define pii pair<int,int>
using namespace std;
vector<pii>frunza[50005];
int mn[50005];
bitset<50005>visited;
priority_queue<pii,vector<pii>,greater<pii> >q;
int n,m,x,y,l;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&l);
        frunza[x].push_back({y,l});
    }
    for(int i=2;i<=n;i++)
        mn[i]=INF;
        q.push({0,1});
    while(!q.empty())
    {
        int ind=q.top().second;
        int cost=q.top().first;
        q.pop();
        if(cost!=mn[ind])
            continue;
        for(int i=0;i<frunza[ind].size();i++)
        {
            if(mn[frunza[ind][i].first]<=cost+frunza[ind][i].second)
                continue;
            mn[frunza[ind][i].first]=cost+frunza[ind][i].second;
            q.push({mn[frunza[ind][i].first],frunza[ind][i].first});
        }
    }
    for(int i=2;i<=n;i++)
    printf("%d ",mn[i]);
    return 0;
}