#include <iostream>
#include <fstream>
#define infinit 1000000000

using namespace std;

int d[1000],pred[1000],viz[1000],n,m;

struct Nod
{
    int v,cost;
    Nod *leg;
};
Nod *L[1000];

void Inserare(int x, int y, int c)
{
    Nod *p;
    p=new Nod;
    p->v=y;
    p->cost=c;
    p->leg=L[x];
    L[x]=p;
}

void Citire()
{   int i,x,y,c;
    ifstream fin("dijkstra.in");
    fin>>n>>m;
    for(i=1;i<m;i++)
    {
        fin>>x>>y>>c;
        Inserare(x,y,c);
    }
    fin.close();
}

void Dijkstra(int s)
{
    int i,pas,minim,k;
    Nod *p;
    //initializari
    for(i=1;i<=n;i++)
    {
        d[i]=infinit;
        pred[i]=viz[i]=0;
    }
    for(p=L[s];p!=NULL;p=p->leg)
    {
        i=p->v;
        d[i]=p->cost;
        pred[i]=s;
    }
    viz[s]=1;
    d[s]=0;


    for(pas=1;pas<n;pas++)
    {
        //determinarea nodului k;
        minim=infinit;
        k=0;
        for(i=1;i<=n;i++)
            if(d[i]<minim && !viz[i])
            {
                minim=d[i];
                k=i;
            }

        if(d[k]==infinit)
            return;

        viz[k]=1;
        for(p=L[k];p!=NULL;p=p->leg)
        {
            i=p->v;
            if(d[i]>d[k]+p->cost)
            {
                d[i]=d[k]+p->cost;
                pred[i]=k;
            }
        }
    }
}

void Drum(int i)
{
    if(i!=0)
    {
        Drum(pred[i]);
        cout<<i<<" ";
    }
}

int main()
{
    Citire();
    Dijkstra(1);
    for(int i=1;i<=n;i++)
    {
        if(d[i]!=infinit)
        {
            cout<<"costul drumului de la 1 la: "<<i;
            cout<<" este: "<<d[i]<<":";
            Drum(i);
            cout<<"\n";
        }
        else
            cout<<"nu este drum\n";
    }
    return 0;
}