#include <iostream>
#include <utility>
#include <set>
#include <fstream>
using namespace std;
class Vertex
{
    int a, b, c;
    friend istream &operator >>(istream &, Vertex &);
    friend ostream &operator <<(ostream &, const Vertex &);
    friend bool operator < (const Vertex &, const Vertex &);
public:
    int get_a() const;
    int get_b() const;
    int get_cost() const;
};

istream &operator >>(istream &in, Vertex &x)
{
    in>>x.a>>x.b>>x.c;
    return in;
}

ostream &operator << (ostream &out, const Vertex &x)
{
    out<<x.a<<" "<<x.b<<" "<<x.c<<'\n';
    return out;
}

bool operator < (const Vertex &x, const Vertex &y)
{
    return x.c<=y.c;
}

int Vertex:: get_a() const
{
    return a;
}

int Vertex:: get_b() const
{
    return b;
}

int Vertex:: get_cost() const
{
    return c;
}

int main()
{
    int Max= 1001;
    int n, m,i ,j, initial = 1, curent;
    set<int> visited, unvisited;
    set< Vertex >  v;
    int *costs;
    Vertex x;
    ifstream f("dijkstra.in");
    ofstream g ("dijkstra.out");
    f>>n>>m;
    for(i=0; i<m; i++)
    {
        f>>x;
        v.insert(x);
    }
    costs = new int[n+1];
    for(i=1;i<=n;i++)
        {
          unvisited.insert(i);
          costs[i] = Max;
        }
    costs[initial]=0;

    /*for(set<Vertex>::  iterator it= v.begin(); it!=v.end(); it++)
            if((*it).get_a()==initial)
               {
                   cout<<"Muchia 1, "<< (*it).get_b()<<" cu costul "<< (*it).get_cost()<<'\n';
                costs[(*it).get_b()]=(*it).get_cost();
                 for(i=2;i<=n;i++)
            cout<<costs[i]<<" ";
   cout<<'\n';
                }
            else
                costs[(*it).get_b()]=Max;*/
    while(!unvisited.empty())
    {  /*               for(i=1;i<=n;i++)
            cout<<costs[i]<<" ";
   cout<<'\n';*/
        curent = *unvisited.begin();
        for(set<Vertex>::  iterator it= v.begin(); it!=v.end(); it++)
               if((*it).get_a()==curent && (*it).get_cost()+costs[curent]<costs[(*it).get_b()])
                          {//cout<<"Costul lui " << (*it).get_b() <<" este "<< costs[(*it).get_b()]<< "iar noul cost este " << (*it).get_cost()+costs[curent] <<'\n';
                costs[(*it).get_b()]=(*it).get_cost()+costs[curent];}
        unvisited.erase(curent);
    }
    for(i=2;i<=n;i++)
        if(costs[i]==1001)
            g<<0<<" ";
        else
            g<<costs[i]<<" ";
    g<<'\n';
    return 0;
}