#include <iostream>
#include <fstream>
#include <list>
#include <sstream>
#include <string>

using namespace std;

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

int n,i,k,j;

struct edge
{
    int node,val;
};

struct t
{
    int parent,dist;
    t():dist(99999){}

}dist[100];

list<edge> a[100];
list<int> active;

void print_list(int i)
{
        for(list<edge>::iterator it= a[i].begin(); it!=a[i].end();it++)
        {
            cout<<"("<<(*it).node<<";"<<(*it).val<<") ";
            //cout<<(*it).node;
        }
        cout<<endl;
}
void dijkstra(int s)
{
    //cout<<active.back()<<endl;
    while(!active.empty())
    {
        int curr_node = active.back();
        //cout<<curr_node<<endl;
        //print_list(curr_node);
        for(list<edge>::iterator it=a[curr_node].begin();it!=a[curr_node].end();it++)
        {

            int val = (*it).val;
            int node = (*it).node;
            //cout<<val<<endl;
            if(dist[node].dist > dist[curr_node].dist + val)
            {
                dist[node].dist = dist[curr_node].dist + val;
                dist[node].parent = curr_node;
                active.push_front(node);
            }
        }
        active.pop_back();
    }
}

void read_list()
{
    string s;
    fin>>n;
    getline(fin,s);
    for(int i=1;i<=n;i++)
    {
        int node,val;
        getline(fin,s);
        istringstream iss(s);
        while(iss >> node >> val)
        {
            //cout<<node<<" "<<val<<endl;
            edge curr= {node,val};
            a[i].push_back(curr);
        }
    }
}

void read_edge()
{
    int m,z,x,c;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>z>>x>>c;
        edge curr = {x,c};
        a[z].push_back(curr);
    }
}

int main()
{
    read_edge();
    /// INIT
    dist[1].dist = 0;
    active.push_front(1);
    dijkstra(1);


    for(int i=1;i<=0;i++)
    {
        cout<<i<<": ";
        for(list<edge>::iterator it= a[i].begin(); it!=a[i].end();it++)
        {
            cout<<"("<<(*it).node<<";"<<(*it).val<<") ";
            //cout<<(*it).node;
        }
        cout<<endl;
    }
    for(int i=2;i<=n;i++) fout<<dist[i].dist<<" ";

}