#include <iostream>
#include <fstream>
using namespace std;
ifstream f("graf.txt");
int v,n,m,d[30],c[30][30],s[30],t[30],poz;

void citire()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
     {
        int x,y,cost;
        f>>x>>y>>cost;
        c[x][y]=c[y][x]=cost;
     }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(i!=j && c[i][j]==0)
            c[i][j]=c[j][i]=32000;
}

void dijkstra()
{
    cout<<"v="; cin>>v;
    s[v]=1;
    for(int i=1;i<=n;i++)
    {
        d[i]=c[v][i];
        if(c[v][i]!=32000 && i!=v)
            t[i]=v;
    }
    for(int k=1;k<n;k++)
    {
    int min=32000;
        for(int j=1;j<=n;j++)
            if(d[j]<min && s[j]==0)
            {
                min=d[j];
                poz=j;
            }
    s[poz]=1;
    for(int i=1;i<=n;i++)
        if(s[i]==0 && c[poz][i]!=32000)
            if(d[i]>d[poz]+c[poz][i])
            {
                d[i]=d[poz]+c[poz][i];
                t[i]=poz;
            }
    }
}

void drum(int i)
{
    if(t[i]!=0)
    {
        drum(t[i]);
        cout<<i<<" ";
    }
    else
        cout<<i<<" ";
}

int main()
{
    citire();
    dijkstra();
    for(int i=1;i<=n;i++)
        if(i!=v)
        {
            cout<<"Costul drumului minim de la "<<v<<" la "<<i<<" este "<<d[i]<<" si trece prin nodurile ";
            drum(i);
            cout<<endl;
        }
}