#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
using namespace std;
#define N 205
#define M 1005
#define fill(x, y) memset(x, y, sizeof(x))
#define LL long long
#define min(x, y) ((x) < (y) ? (x) : (y))
const LL INF = 1e+18;
LL state[N];
int ls[M], n, m, k, st, ed, path[N];
int vexnum, edge;
bool exits[N];
struct dis
{
    int to, w, next;
}e[M];
int l = 0;
struct cmp
{
    int operator()(int a, int b)
    {
        return state[a] > state[b];
    }
};
bool check(int Vexnum, int edge) {
    if (Vexnum <= 0 || edge <= 0 || ((Vexnum * (Vexnum - 1)) / 2) < edge)
        return false;
    return true;
}
inline int read()
{
    int x = 0, p = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') p = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * p;
}
void write(LL x)
{
    if (x < 10)
    {
        putchar(x + '0');
        return;
    }
    else
    {
        write(x / 10);
        write(x % 10);
    }
}
void print(int s)
{
    stack<int> q;
    for(int i = 1;i <= vexnum; i++)
    {
        int p = i;
        while( path[p] != -1)
        {
            q.push(p);
            p = path[p];
        }
        q.push(p);
        cout << s << "-->" << i << " ";
        cout << "dis" << ":" << state[i] << " " << s;
        q.pop();
        while(!q.empty())
        {
            cout<<"-->"<<q.top();
            q.pop();
        }
        cout<<endl;
    }
}
void creadGrath()
{
    printf("输入各条边:\n");
    for (int i = 1; i <= edge; i++)
    {
        int x = read(), y = read(), w = read();
        e[++l] = dis {y, w, ls[x]};
        ls[x] = l;
        e[++l] = dis{ x, w, ls[y] };
        ls[y] = l;
    }
}
void Dij(int st)
{
    memset(path, -1, sizeof(path));
    priority_queue<int, vector<int>, cmp > t;
    for (int i = 1; i <= vexnum; i++)
        state[i] = INF;
    exits[st] = 1;
    t.push(st);
    state[st] = 0;
    while (!t.empty())
    {
        int now = t.top();
        t.pop();
        for (int i = ls[now]; i; i = e[i].next)
        {
            if (state[e[i].to] > state[now] + e[i].w)
            {
                path[e[i].to] = now;
                state[e[i].to] = state[now] + e[i].w;
                if (!exits[e[i].to])
                {
                    exits[e[i].to] = 1;
                    t.push(e[i].to);
                }
            }
        }
        exits[now] = 0;
    }
}
int main()
{
    printf("输入图的顶点个数和边的条数：\n");
    vexnum = read();
    edge = read();
    while (!check(vexnum, edge))
    {
        printf("输入的数值不合法，请重新输入\n");
        vexnum = read();
        edge = read();
    }
    creadGrath();
    for (int i = 1; i <= vexnum; i++)
    {
        Dij(i);
        print(i);
    }
}