#include <iostream>
#include <fstream>
using namespace std;

ifstream f("dijkstra.in");
int d[20],s[20],t[20], n, m, x, y, c, a[20][20];

void citire()
{
    f >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i == j)
                a[i][j] = 0;
        else
            a[i][j] = 1000;

        for(int i = 0; i < m; i++)
        {
            f >> x >> y >> c;
            a[x][y] = c;
        }

}

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

void dijkstra(int r)
{
    int i, poz, k, mini;
    for(i = 1; i <= n; i++)
    {
        d[i] = a[r][i];
        if(i != r && d[i] < 1000)
            t[i] = r;
    }
    s[r] = 1;
    for(k = 1; k < n; k++)
    {
        mini = 1000;
        for(i = 1; i <= n; i++)
            if(s[i] == 0 && d[i] < mini)
        {
            mini = d[i];
            poz = i;
        }
        s[poz] = 1;
        for(i = 1; i <= n; i++)
            if(s[i] == 0)
                if(d[i] > d[poz] + a[poz][i])
                {
                    d[i] = d[poz]+a[poz][i];
                    t[i] = poz;
                }
    }
}



int main()
{
    citire();
    int r = 1;
    dijkstra(r);
    for(int i = 1; i <= n; i++)
        if(i != r && d[i] < 1000)
        {
        cout << r << "->" << i <<  ": ";
        drum(i);
        cout << "=" << d[i] <<endl;
        }
}