#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= 2147483647;
    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=2;i<=n;i++)
         unvisited.insert(i);
    costs[initial]=0;
    for(set<Vertex>::  iterator it= v.begin(); it!=v.end(); it++)
            if((*it).get_a()==initial)
            {
                costs[(*it).get_b()]=(*it).get_cost();
                v.erase(it);
            }
            else
                costs[(*it).get_b()]=Max;
    while(!unvisited.empty())
    {
        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()])
            {
                costs[(*it).get_b()]=(*it).get_cost()+costs[curent];
                //v.erase(it);
            }
        unvisited.erase(curent);
    }
    for(i=2;i<=n;i++)
        g<<costs[i]<<" ";
    g<<'\n';
    return 0;
}