#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;
}


void calculeaza (int curent, set<Vertex> v, int costs[], int visited[])
{
            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];
                        if(visited[(*it).get_b()]==1)
                            calculeaza((*it).get_b(), v, costs, visited);
                    }
}



int main()
{
    int Max= 1001;
    int n, m,i, initial = 1;
    int *visited;
    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];
    visited = new int[n+1];
    for(i=1;i<=n;i++)
        {
          visited[i]=0;
          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;*/
    for(i=1;i<=n;i++)
    {
        visited[i]=1;
        calculeaza (i, v, costs, visited);
    }
    for(i=2;i<=n;i++)
        if(costs[i]==1001)
            g<<0<<" ";
        else
            g<<costs[i]<<" ";
    g<<'\n';
    return 0;
}