Problem:


Sports Days 2.0

会津大学附属小学校（会津大小）は日本有数の競技プログラマー養成校として有名である。
もちろん、運動会に参加しているときでさえアルゴリズムの修行を欠かせない。
競技プログラミング部部長のあなたはもちろんこの大会でも勝利したい。
今回はある競技に注目する。

ある競技とは会津大小で行われている伝統的な競技だ。
校庭にコーンがV個置いてある。
コーンのいくつかのペアは白線で描かれた矢印で結ばれている。
矢印の先は片側だけについており、整数が併記されている。
同じコーンのペアがの複数の矢印に結ばれている場合もある。

競技者は任意にコーンを選び、移動開始する。
移動は競技者がいるコーンから矢印の上をその向きに移動し、次のコーンへ移る。
同じコーン、同じ矢印を何度も辿っても良い。
競技者はコーンからコーンへの移動後、さらに移動するか移動を終了をするかを選択することができる。

この競技の目的は矢印を辿ることにより、スコアをK以上にすることである。
スコアは矢印を辿る度に併記された整数値が加算されていく。
より少ない経由する矢印の本数でスコアをK以上にした競技者が勝利となる。
矢印が同じ本数の場合はより高いスコアの競技者が勝利となる。

このルールで最適な動きを競技者が行った場合、何本の矢印を経由すべきか出力せよ。
また、経由した矢印の数が100本以下の場合、経由すべきコーンを順にすべて出力せよ。
最適な動きが複数存在する場合があるが、どの動きの結果を出力しても良い。
スコアをK以上にする動きが存在しない場合は-1を出力せよ。

また、コーンにはすべて0からV-1までの番号が振られており、
色はすべて緑色（意味深）である。

Input

入力は以下の形式で与えられる。

 V E K

v11 v12 c1
...
vi1 vi2 ci
...
vE1 vE2 cE

ここで、

Vはコーンの数

Eは矢印の数

vi,1は矢印iの始点のコーン番号

vi2は矢印iの終点のコーン番号

ciは矢印に併記されている整数

である。

Constraints

入力は以下の条件を満たす。

入力はすべて整数

2≤V≤150

0≤E≤V&times;V

0<K≤106

0≤ vi1, vi2 < V      (0<i≤E)

vi1 &ne; vi2 (0<i≤E)

0<ci ≤ 100           (0<i≤E)

vi1 = vj1 かつ vi2 = vj2 (i &ne; j, 0<i,j≤E)となるようなi, jが含まれる入力も存在する。

Output

出力は2行からなる。

1行目　最適な動きを行った場合の経由する矢印の本数で出力

2行目　経由すべきコーンの番号を経由する順番に空白区切りで出力

最適な動きが複数存在する場合があるが、どの動きの結果を出力しても良い。
経由すべき矢印の本数が100本を越える場合、2行目は出力してはいけない。
スコアをK以上にする最適な動きが存在しない場合は-1を1行目に出力し、
2行目に何も出力してはいけない。

Sample Input 1

3 9 89
2 0 2
1 0 3
2 0 1
2 0 3
0 1 1
0 1 2
1 2 3
0 1 1
1 0 2

Output for the Sample Input 1

34
1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 0

Sample Input 2

2 0 1

Output for the Sample Input 2

-1

Sample Input 3

7 8 4000
0 1 1
1 0 1
1 2 2
2 3 2
3 4 2
5 4 3
3 5 4
5 6 5

Output for the Sample Input 3

3991



Sample input:
3 9 89
2 0 2
1 0 3
2 0 1
2 0 3
0 1 1
0 1 2
1 2 3
0 1 1
1 0 2


Sample output:
34
1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 0

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N, M, K = map(int, readline().split())
    INF = 10**18
    E = [[-INF]*N for i in range(N)]
    for i in range(M):
        a, b, c = map(int, readline().split())
        E[a][b] = max(E[a][b], c)
    G = [[] for i in range(N)]
    for v in range(N):
        for w in range(N):
            if E[v][w] >= 0:
                G[v].append((w, E[v][w]))
    T = 100
    dist = [[0]*(T+1) for i in range(N)]
    prv = [[None]*(T+1) for i in range(N)]
    que = []
    for i in range(N):
        que.append((0, i, 0))
    t0 = T+1
    while que:
        cost, v, t = heappop(que)
        cost = -cost
        if cost >= K and t < t0:
            t0 = t
        if cost < dist[v][t] or t == T:
            continue
        for w, d in G[v]:
            if dist[w][t+1] < cost + d:
                dist[w][t+1] = cost + d
                prv[w][t+1] = v
                heappush(que, (-(cost + d), w, t+1))
    if t0 != T+1:
        v0 = 0; d = 0
        for v in range(N):
            e = dist[v][t0]
            if d < e:
                d = e
                v0 = v
        res = [v0]
        v = v0; t = t0
        while t > 0:
            v = prv[v][t]; t -= 1
            res.append(v)
        res.reverse()
        write("%d\n" % t0)
        write(" ".join(map(str, res)))
        write("\n")
        return

    for v in range(N):
        E[v][v] = 0
    E2 = [[-INF]*N for i in range(N)]
    A = (K-1).bit_length()
    RS = [E]
    for k in range(A):
        F = [[-INF]*N for i in range(N)]
        for v in range(N):
            for w in range(N):
                E2[w][v] = E[v][w]
        ok = 0
        for i in range(N):
            Ei = E[i]
            for j in range(N):
                Ej = E2[j]
                F[i][j] = r = max((a+b for a, b in zip(Ei, Ej) if a >= 0 and b >= 0), default = -INF)
                if r >= K:
                    ok = 1
        RS.append(F)
        E = F
        if ok:
            A = k
            break

    D = [0]*N
    ans = 0
    for i in range(A, -1, -1):
        E = RS[i]
        D0 = [0]*N
        ok = 0
        for v in range(N):
            D0[v] = r = max((a + e[v] for a, e in zip(D, E) if e[v]), default = -INF)
            if r >= K:
                ok = 1
        if not ok:
            ans += 1 << i
            D = D0
    ans += 1
    if ans > K:
        write("-1\n")
    else:
        write("%d\n" % ans)
solve()