#include <bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define N 500005
#define INF 12600000000
using namespace std;
typedef long long ll;
FILE *fin=fopen("dijkstra.in","r");
FILE *fout=fopen("dijkstra.out","w");
ll n, m, i, j, x, y, p, ans[N], nrv, dmin, nod;
set<int> viz;
vector<pair<int,int> >v[N];
void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
}
int main()
{
    fast();
    fscanf(fin,"%Ld%Ld",&n,&m);
    for(i=1;i<=m;++i)
        {
            fscanf(fin,"%Ld%Ld%Ld",&x,&y,&p);
            v[x].pb({y,p});
        }
    for(i=1;i<=n;i++)
        viz.insert(i);
    for(i=1;i<=n;i++)
        ans[i]=INF;
    ans[1]=0;
    nrv=n;
    while(nrv)
    {
        dmin=INF+1;
        for(auto i : viz)
            if(ans[i]<dmin)
            {
                dmin=ans[i];
                nod=i;
            }
        for(auto i:v[nod])
            ans[i.st]=min(ans[i.st],ans[nod]+i.nd);
        viz.erase(viz.find(nod));
        nrv--;
    }
    for(i=2;i<=n;i++)
        fprintf(fout,"%d ",ans[i]);
    return 0;
}