题目描述

给定 $n$ 个点、$m$ 条边的有向图和一个根节点 $r$，求以 $r$ 为根的最小边权和外向树形图的边权和并输出一个这样的树形图。如果不存在这样的树形图输出 -1。

输入格式

第一行三个整数 $n,m,r$，接下来 $m$ 行每行三个整数 $u,v,w$ 表示有一条从 $u$ 到 $v$、边权为 $w$ 的有向边。可能存在重边自环。

输出格式

如果不存在树形图，输出一行 -1；否则第一行输出一个整数表示最小树形图边权和，第二行输出 $n-1$ 个整数，表示最小树形图上的 $n-1$ 条边。如果有多种方案，输出任意一种。

由于出题人不会写 spj，如果你只准备做第一问，那么在第二问内也请你输出 $n-1$ 个在 $[1,m]$ 中的数，否则你会在该测试点获得 $0$ 分的好成绩。

样例输入 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

样例输入 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

样例输入 3

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

样例输出 3

-1

数据范围

共有两档部分分，每档各 50 分，每档部分分内分数均分。

在某组数据中，如果你正确回答了第一行的问题但没有正确回答第二行的问题，则只会得到该测试点 $60\%$ 的分数。

对于前 5 个测试点，满足 $1 \leq n \leq 10^3 , 1 \leq m \leq 10^4$；

对于后 10 个测试点，满足 $1 \leq n \leq 10^5 , 1 \leq m \leq 10^6$。

对于所有数据满足 $1 \leq u,v \leq n , 1 \leq w \leq 10^9$。

时间限制：$2$ s

空间限制：$512$ MB