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

#define MAXINT 9999999

using namespace std;

struct node
{
    int to,val;
};

struct comparator
{
    bool operator() (int i, int j)
    {
        if(i<j)
            return false;
        return true;
    }
};

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;
typedef priority_queue<int,vector<int>,comparator> HEAP;

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

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

    VECTOR_OF_INTS visited(n+3,0);

    dist[s] = 0;

    while(!active.empty())
    {
        //if(visited[active.front()]==0)
        int curr = active.top();
        active.pop();

        for(LIST_OF_NODES::iterator it = a[curr].begin(); it != a[curr].end(); it++)
        {
            int to = (*it).to;
            int val = (*it).val;
            if(dist[to] > dist[curr]+val)
            {
                dist[to] = dist[curr]+val;
                active.push(to);
            }
        }
        visited[curr] = 1;

    }
}

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,MAXINT);
    dijkstra(a,curr_dist,n,1);
    for(int i=2;i<=n;i++)
        if(curr_dist[i] == MAXINT)
            fout<<"0 ";
        else
            fout<<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;
    }
    */

}