#include<iostream>
#include<fstream>
#include<vector>
#include<deque>
#define NMAX 50010
using namespace std;
fstream fin("dijkstra.in",ios::in),fout("dijkstra.out",ios::out);
int cost[NMAX];
deque <int> d;
vector<pair<int,int> >v[NMAX];
void bfs()
{
    int i,nod,b,c;
    d.push_back(1);
    while(!d.empty())
    {
        nod=d.front();
        for(i=0;i<v[nod].size();i++)
        {
            b=v[nod][i].first;
            c=v[nod][i].second;
            if(cost[b]>cost[nod]+c || cost[b]==0)
            {
                cost[b]=cost[nod]+c;
                d.push_back(b);
            }
        }
        d.pop_front();
    }
}
int main()
{
    int i,j,a,b,c,n,m;
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
    }
    bfs();
    for(i=2;i<=n;i++)
    {
        fout<<cost[i]<<" ";
    }
}