#include <bits/stdc++.h>
#define inf 99999999
using namespace std;
typedef pair<int,int> pereche;
int i,j,n,m,x,y,z,d[50001],cst,nd,a;
priority_queue <pereche ,vector <pereche>, greater<pereche>  > q;
vector <pereche>v[250001];
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back({y,z});
    }
    for(i=2;i<=n;i++)
        d[i]=inf;
    q.push({0,1});
    while(!q.empty())
    {
        cst=q.top().first;
        nd=q.top().second;
        q.pop();
        for(i=0;i<v[nd].size();i++)
            if(cst+v[nd][i].second<d[v[nd][i].first])
        {
            d[v[nd][i].first]=cst+v[nd][i].second;
            q.push({ d[v[nd][i].first],v[nd][i].first});
        }
    }
    for(i=2;i<=n;i++)
        printf("%d ",d[i]);
    return 0;
}