#include <bits/stdc++.h>
#define maxim 50005
#define inf 10000
using namespace std;

    vector <pair<int,int> > graf[maxim];
    queue <int> coada;

    ifstream fin("bfs.in");
    ofstream fout("bfs.out");

    int n, m, x, y, z, cost[maxim];
    int viz[maxim];
int main()
{
        fin>>n>>m;
        for(int i=1;i<=n;i++)
            cost[i]=inf;
        for(int i=1;i<=m;i++)
        {
            fin>>x>>y>>z;
            graf[x].push_back({y,z});
        }
        cost[1]=0;
        coada.push(1);
        viz[1]=1;
        while(!coada.empty())
        {
            int actualNod=coada.front();
            coada.pop();
            for(int i=0;i<graf[actualNod].size();i++)
            {
                if(viz[graf[actualNod][i].first]<n && cost[graf[actualNod][i].first]>cost[actualNod]+graf[actualNod][i].second)
                {
                    viz[graf[actualNod][i].first]+=1;
                    cost[graf[actualNod][i].first]=cost[actualNod]+graf[actualNod][i].second;
                    coada.push(graf[actualNod][i].first);
                }
            }
        }
        for(int i=2;i<=n;i++)
        {
            fout<<cost[i]<<" ";
        }
    return 0;
}