def get_equal_vertices(trails_for_hats, dual_solution):
    equal_vertices = [False for _ in trails_for_hats]
    for hat, trails_for_hat in enumerate(trails_for_hats):
        trails_budget = sum([dual_solution[trail] for trail in trails_for_hat])
        if trails_budget == costs[hat]:
            equal_vertices[hat] = True
    return equal_vertices


def is_vertex_cover(equal_vertices, trails):
    for trail_id, (u, v, w) in enumerate(trails):
        if (not equal_vertices[u] and
                not equal_vertices[v] and
                not equal_vertices[w]):
            return False, trail_id
    return True, None

n, m = map(int, input().split())
costs = [int(c_i) for c_i in input().split()]
trails = []
trails_for_hats = [[] for _ in range(n)]
for i in range(m):
    u, v, w = map(int, input().split())
    trails.append((u - 1, v - 1, w - 1))
    trails_for_hats[u - 1].append(i)
    trails_for_hats[v - 1].append(i)
    trails_for_hats[w - 1].append(i)

dual_solution = [0 for _ in range(m)]
equal_vertices = get_equal_vertices(trails_for_hats, dual_solution)
are_all_covered, uncovered_trail = is_vertex_cover(equal_vertices, trails)
while not are_all_covered:
    min_cost = min(costs[trails[uncovered_trail][0]],
                   costs[trails[uncovered_trail][1]],
                   costs[trails[uncovered_trail][2]])
    dual_solution[uncovered_trail] += min_cost
    equal_vertices = get_equal_vertices(trails_for_hats, dual_solution)
    are_all_covered, uncovered_trail = is_vertex_cover(equal_vertices, trails)
print(sum(equal_vertices))
for i, is_in_cover in enumerate(equal_vertices):
    if is_in_cover:
        print(i + 1, end=' ')
print()
for y_e in dual_solution:
    print(y_e, end=' ')