#!/usr/bin/python
from __future__ import print_function
import sys
import random


def randomgraph(n, m, o=10, p=1):
    rv = []
    existing = set()

    for i in range(m):
        u = v = None
        while u == v or (u, v) in existing:
            u, v = random.choice(n), random.choice(n)
        existing.add((u, v))
        rv.append((u, v, random.randrange(o)-p))

    return rv

def floydwarshall(edges):
    V = {u for u, v, w in edges} | {v for u, v, w in edges}
    inf = float('inf')
    d = {(i, j): inf for i in V for j in V}

    for u, v, w in edges:
        d[u, v] = min(d[u, v], w)

    # Sorted order so that cases where the algorithm doesn't give
    # incorrect results at least get repeatable results:
    for k in sorted(V):
        for i in sorted(V - {k}):
            for j in sorted(V - {k}):
                d[i, j] = min(d[i, j], d[i, k] + d[k, j])

    return d

def dictprint(nodes, edges):
    print('  ' + ' '.join('%3.3s' % node for node in nodes))
    for i in nodes:
        print('%s ' % i + ' '.join('%3.3s' % edges.get((i, j), '?')
                                    for j in nodes))

def gdict(edges):
    return {(u, v): w for u, v, w in edges}

def graphvizprint(edges):
    print('digraph G {rankdir=LR;'
           + ''.join('%s->%s[label="%s"];' % (u, v, w)
                     for u, v, w in edges)
           + '}')

def number(s):
    try:
        return int(s)
    except ValueError:
        return float(s)

if __name__ == '__main__':
    if len(sys.argv) == 1:
        nodes = list('abcde')
        G = randomgraph(nodes, 10)
    else:
        G = list(zip(sys.argv[1::3], sys.argv[2::3], map(number, sys.argv[3::3])))
        nodes = sorted({u for u, v, w in G} | {v for u, v, w in G})

    dictprint(nodes, gdict(G))
    print()
    dictprint(nodes, floydwarshall(G))
    graphvizprint(G)
    print(sys.argv[0] + ' ' + ' '.join('%s %s %s' % arc for arc in G))