#include <iostream>
#include <fstream>
#include <queue>
#define MAX_NODES 300
#define INFINITY 99999
using namespace std;

class Node
{
private:
    int to,cost;
    Node *next;
public:
    Node(){next=NULL;}
friend class List;
friend class Graph;
};
class List
{
private:
    Node *first,*last;
public:
    List()
    {first=last=NULL;}
    void addNode(int to,int cost)
    {
        Node *c=new Node;
        c->to=to;
        c->cost=cost;
        if(first==last && first==NULL)
        {
            first=last=c;
        }
        else
        {
            last->next=c;
            last=c;
        }
    }
    friend class Graph;
};
class Graph
{
private:
    List nodes[MAX_NODES];
    int n,m;
public:
    void addEdge(int from,int to,int cost)
    {
        nodes[from].addNode(to,cost);
    }
    void dijkstra(const char *filename)
    {
        int *a=new int[n+1];
        fill(a,a+n+1,INFINITY);
        a[1]=0;
        queue<int>Q;
        Q.push(1);
        while(!Q.empty())
        {
            int nd=Q.front();
            Q.pop();
            for(Node *i=nodes[nd].first;i!=NULL;i=i->next)
            {
                if(a[nd]+i->cost<a[i->to])
                {
                    a[i->to]=a[nd]+i->cost;
                    Q.push(i->to);
                }
            }
        }
        ofstream fout(filename);
        for(int i=2;i<=n;i++)
            fout<<a[i]<<" ";
    }
    void read(const char* filename)
    {
        ifstream fin(filename);
        fin>>n>>m;
        for(int j=1;j<=m;j++)
        {
            int from,to,cost;
            fin>>from>>to>>cost;
            addEdge(from,to,cost);
        }
    }
};
int main()
{
    Graph g;
    g.read("dijkstra.in");
    g.dijkstra("dijkstra.out");
    return 0;
}