题目描述

这是一道模板题。

给定包含 $n$ 个结点，$m$ 条有向边的一个有向带权图。试求一棵以结点 $r$ 为根的最小树形图，输出最小树形图每条边的权值之和，并输出任一种方案；如果没有以 $r$ 为根的树形图，输出 -1。

输入格式

第一行包含三个整数 $n,m,r$，意义同题目所述。$(1\le n\le 3\times 10^5,0\le m\le 10^6,1\le r\le n)$

接下来 $m$ 行，每行包含三个整数 $u,v,w$，表示图中存在一条从 $u$ 指向 $v$ 的权值为 $w$ 的有向边。$(1\le u,v\le n,u\ne v,1\le w\le 10^9)$

输出格式

如果原图中存在以 $r$ 为根的最小树形图，就输出最小树形图每条边的权值之和，否则输出 -1。

如果输出不是 -1，还要输出一行 $n-1$ 个整数，为最小树形图中的边在输入中的编号（从 $1$ 开始）。

样例输入输出

样例输入1

4 6 1
1 2 3
1 3 1
4 1 2
4 2 2
3 2 1
3 4 1

样例输出 1

3
2 5 6

样例 1 解释

最小树形图中包含第 $2,5,6$ 三条边，总权值为 $1 + 1 + 1 = 3$。

样例输入 2

4 6 3
1 2 3
1 3 1
4 1 2
4 2 2
3 2 1
3 4 1

样例输出 2

4
3 5 6

样例 2 解释

最小树形图中包含第 $3,5,6$ 三条边，总权值为 $2 + 1 + 1 = 4$

样例输入 3

4 6 2
1 2 3
1 3 1
4 1 2
4 2 2
3 2 1
3 4 1

样例输出 3

-1

样例 3 解释

无法构成最小树形图，故输出 $-1$。