#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int oo = 20000;
const int NMAX = 50000;
vector < pair < int, int > > laturi[NMAX];
int n,m;
int Distante[NMAX];
bool inCoada[NMAX];
void Citire(){
    int x,y,c;
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>c;
        laturi[x].push_back(make_pair(y,c));
    }
}
void Afisare(){
    for(int i=2;i<=n;i++)
    {
        if(Distante[i]!= oo)out<<Distante[i]<<" ";
        else out<<"0 ";
    }
    out<<"\n";
}
struct _compara
{
    bool operator()(int x, int y)
    {
        return Distante[x] > Distante[y];
    }
};
priority_queue < int, vector<int>, _compara> tail;
void Dijkstra(int nodStart){
    for(int i=1;i<=n;i++)
    {
        Distante[i] = oo;
    }

    tail.push(nodStart);
    inCoada[nodStart] = true;
    Distante[nodStart] = 0;
    int nod_cur,cost_cur,vecin_cur;
    while(!tail.empty())
    {
        nod_cur = tail.top();
        tail.pop();
        inCoada[nod_cur] = false;
        for(int i=0;i < laturi[nod_cur].size();i++)
        {
            vecin_cur = laturi[nod_cur][i].first;
            cost_cur = laturi[nod_cur][i].second;
            if(Distante[nod_cur] + cost_cur < Distante[vecin_cur])
            {
                Distante[vecin_cur] = Distante[nod_cur] + cost_cur;
                if(!inCoada[vecin_cur])
                {
                inCoada[vecin_cur] = true;
                tail.push(vecin_cur);
                }
            }
        }
    }
}
int main()
{
 Citire();
 Dijkstra(1);
 Afisare();
return 0;
}