#include <iostream>
#include <fstream>
#include <vector>
#include <list>

#define MAXINT 9999999
#define cout fout

using namespace std;

struct node
{
    int to,val;
};

typedef list<node> LIST_OF_NODES;
typedef vector<LIST_OF_NODES> VECTOR_OF_LISTS_OF_NODES;
typedef list<int> LIST_OF_INTS;
typedef vector<int> VECTOR_OF_INTS;
typedef vector<vector<int> > VECTOR_OF_VECTORS_OF_INTS;

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

void dijkstra(VECTOR_OF_LISTS_OF_NODES &a, VECTOR_OF_INTS &dist, int n, int s)
{
    LIST_OF_INTS active;
    active.push_back(s);


    dist[s] = 0;

    while(!active.empty())
    {
        int curr = active.front();
        for(LIST_OF_NODES::iterator it = a[curr].begin(); it != a[curr].end(); it++)
        {
            int from = curr;
            int to = (*it).to;
            int val = (*it).val;
            if(dist[to] > dist[curr]+val)
            {
                dist[to] = dist[curr]+val;
                active.push_back(to);
            }
        }
        active.pop_front();
    }
}

int main()
{
    int n,m;
    fin>>n>>m;
    VECTOR_OF_LISTS_OF_NODES a(n+3);
    //VECTOR_OF_VECTORS_OF_INTS dist(n+3, VECTOR_OF_INTS(n+3));

    for(int i=1;i<=m;i++)
    {
        node curr;
        int from,to,val;
        fin>>from>>to>>val;
        curr.to = to;
        curr.val = val;
        a[from].push_back(curr);
        //curr.to = from;
        //a[to].push_back(curr);
    }

    for(int i=1;i<=0;i++)
    {
        cout<<i<<": ";
        for(LIST_OF_NODES::iterator it=a[i].begin(); it!= a[i].end(); it++)
            cout<<"("<<(*it).to<<";"<<(*it).val<<") ";
        cout<<endl;
    }

    VECTOR_OF_INTS curr_dist(n+3);
    dijkstra(a,curr_dist,n,1);
    for(int i=2;i<=n;i++)
        cout<<curr_dist[i]<<" ";

    return 0;
    /*
    for(int i=1;i<=n;i++)
        dist[i] = dijkstra(a,n,i);

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            cout<<dist[i][j]<<" ";
        cout<<endl;
    }
    */

}