import random, sys

maxn = 1000
maxm = 100000
maxc = 300
maxl = 1000000000

def gen(g, c, name):
    if len(g) not in range(2,maxn+1): raise ValueError("Bad node count")
    if len(c) not in range(1,maxc+1): raise ValueError("Bad client count")

    m = 0
    for i in range(0,len(g)):
        m += len(g[i])
        nbrs = set()
        for u,v,w in g[i]:
            if type(u) != int or type(v) != int or type(w) != int:
                raise ValueError("Bad edge types")

            if u != i: raise ValueError("Loop")

            if w not in range(1,maxl+1): raise ValueError("Bad edge length")

            if u != i or v not in range(0, len(g)): raise ValuError("Bad edge index")

            if v in nbrs: raise ValueError("Parallel edges")
            nbrs.add(v)

    if m > maxm: raise ValueError("Too many edges")

    seen = set()
    def dfs(v):
        if v not in seen:
            seen.add(v)
            for a,b,c in g[v]: dfs(b)
    dfs(0)

    # implicitly ensures each client is of type int
    if not c.issubset(seen): raise ValueError("Clients not reachable")
    if 0 in c: raise ValueError("Depot cannot be client")

    out = open(name, "w")

    print(len(g), m, len(c), file=out)
    print(*c, file=out)

    for l in g:
        for e in l: print(*e, file=out)
    out.close()

def sample1(name):
    g = [[(0,1,1),(0,3,1), (0,2,2)], [(1,2,1)], [], [(3,2,1)]]
    c = {1,2,3}
    gen(g, c, name)

def sample2(name):
    g = [[(0,1,1),(0,3,1), (0,2,1)], [(1,2,1)], [], [(3,2,1)]]
    c = {1,2,3}
    gen(g, c, name)

def sample3(name):
    g = [[] for i in range(8)]
    c = {1, 6, 3, 7, 4}

    g[0] = [(0, 1, 5), (0, 4, 1), (0, 2, 2), (0, 6, 6)]
    g[2] = [(2, 3, 1), (2, 6, 3)]
    g[3] = [(3, 5, 7)]
    g[4] = [(4, 1, 5), (4, 6, 4)]
    g[5] = [(5, 7, 3)]
    g[6] = [(6, 5, 6)]
    gen(g, c, name)

# a line with random edge lengths
# a client is at the end, the rest are random
def line(n, nc, name):
    g = []
    for i in range(0,n-1):
        g.append([])
        g[i].append((i,i+1,random.randrange(1,maxl+1)))
    g.append([])
    c = {n-1}
    lst = list(range(1,n-1))
    random.shuffle(lst)
    c = c.union(lst[:nc-1])

    gen(g, c, name)

def shuffle(g, c):
    perm = list(range(1, len(g)))
    random.shuffle(perm)
    perm = [0] + perm

    cc = {perm[i] for i in c}

    gg = [[] for l in g]

    for l in g:
        for u,v,w in l:
            gg[perm[u]].append((perm[u], perm[v], w))
    return gg, cc

# a line, but with some potential "shortcut" edges
def sh_line(n, m, nc, name):
    g = [[] for i in range(n)]
    gs = [set() for i in range(n)]

    for i in range(0,n-1):
        g[i].append((i,i+1,random.randrange(1,maxl+1)))
        gs[i].add(i+1)

    c = {n-1}
    lst = list(range(1,n-1))
    random.shuffle(lst)
    c = c.union(lst[:nc-1])

    fail = 0
    for i in range(m-n+1):
        while fail < 1000000: # good enough instance if we fail too much
            u,v,w = random.randrange(0,n), random.randrange(0,n), random.randrange(1, 2*maxl//3)
            if u != v and v not in gs[u]: break
            fail += 1
        g[u].append((u,v,w))
        gs[u].add(v)

    gg,cc = shuffle(g, c)
    gen(gg, cc, name)

# random instance:
# construct random shortest path tree by attaching vertex u
# to a random edge from a previous vertex
# then start adding random edges, some being shortest path some not
def rand_g(n, m, nc, name):
    lst1 = list(range(1, 2*n//3))
    random.shuffle(lst1)
    lst2 = list(range(2*n//3, n))
    random.shuffle(lst2)

    lst = lst2 + lst1
    c = set(lst[:nc])

    d = [0]*n
    g = [[] for i in range(n)]
    gs = [set() for i in range(n)]

    for i in range(1,n):
        u = random.randrange(0,i)
        w = random.randrange(1, min(maxl//10, maxl//n))
        g[u].append((u,i,w))
        gs[u].add(i)
        d[i] = d[u] + w

    fail = 0
    for i in range(m-n+1):
        while fail < 1000000: # good enough instance if we fail too much
            u,v = random.randrange(0,n), random.randrange(0,n)
            w = min(maxl-1,max(d[v] - d[u], 1)) + random.randrange(0,2)
            if u != v and v not in gs[u]: break
            fail += 1
        g[u].append((u,v,w))
        gs[u].add(v)


    gg,cc = shuffle(g, c)
    gen(gg, cc, name)



if __name__ == "__main__":

    sys.setrecursionlimit(2*maxn)

    cno = 0

    def next_name():
        global cno

        cno += 1
        return "rm16-delivery-{0:02}.in".format(cno)

    def biggest_m(n):
        return min(n*(n-1), maxm)

    sample1(next_name())
    sample2(next_name())
    sample3(next_name())

    line(10, 1, next_name())
    line(10, 9, next_name())
    line(maxn, 1, next_name())
    line(maxn, maxc-1, next_name())
    line(maxn, maxc//3, next_name())

    sh_line(10, 20, 1, next_name())
    sh_line(10, 40, 1, next_name())
    sh_line(10, 20, 9, next_name())
    sh_line(10, 40, 9, next_name())
    sh_line(maxn, maxm, 1, next_name())
    sh_line(maxn, maxm//10, maxc-1, next_name())
    sh_line(maxn, maxm//10, maxc-1, next_name())
    sh_line(maxn, maxm//10, maxc//3, next_name())
    sh_line(maxn, maxm//2, maxc//3, next_name())

    rand_g(10, 20, 1, next_name())
    rand_g(10, 40, 1, next_name())
    rand_g(10, 20, 9, next_name())
    rand_g(10, 40, 9, next_name())
    rand_g(maxn, maxm, 1, next_name())
    rand_g(maxn, maxm//10, maxc-1, next_name())
    rand_g(maxn, maxm//10, maxc-1, next_name())
    rand_g(maxn, maxm//10, maxc//3, next_name())
    rand_g(maxn, maxm//2, maxc//3, next_name())
    rand_g(maxn, maxn-1, maxc, next_name())
    rand_g(maxn, maxn-1, maxc, next_name())
    rand_g(maxn, maxn-1, maxc, next_name())