题目内容

外卖骑手需要在有限的工作时间内规划配送路线，以获取尽可能多的收入。地图中的地点统一用编号表示，每笔订单由三个信息描述：出发地点 $s$、目的地点 $d$ 和配送收入 $p$。

骑手从某个地点出发。当他位于地点 $u$ 时，可以选择一笔从 $u$ 发出且尚未配送的订单，将它送至目的地点 $v$。完成这次配送会消耗 1 单位时间，并获得该订单对应的收入。随后骑手位于 $v$，可以继续选择从 $v$ 发出的订单进行下一次配送。若有多笔订单的出发地点和目的地点完全相同，则这些订单可以合并配送：它们只消耗 1 单位时间，骑手获得的收入为这些订单收入之和。每笔订单最多只能被配送一次。

骑手的工作总时间为 $t$。如果剩余工作时间等于 0，或者当前所在地点没有尚未配送的、从该地点发出的订单，配送过程立即结束。

给定骑手的初始出发地点编号 $S_n$、工作总时间 $t$ 以及全部订单，请计算骑手能够获得的最大收入，并给出对应的配送路线。配送路线表示为骑手依次经过的地点编号序列，初始地点编号为 $S_n$。如果存在多条路线获得相同的最大收入，则输出地点编号序列字典序最小的那一条。

输入描述

第一行包含两个整数 $S_n$ 和 $t$，分别表示骑手初始所在的地点编号和可用的工作总时间。
第二行包含一个整数 $M$，表示订单的数量。
接下来 $M$ 行，每行包含三个整数 $s$、$d$ 和 $p$，依次表示一笔订单的出发地点编号、目的地点编号和配送收入。

约束条件：

$0 < M \leq 10^4$

$0 \leq s < N$

$0 \leq d < N$

$0 < p \leq 10^4$

$0 \leq S_n < N$

$1 \leq t \leq 10^4$

输出描述

第一行输出一个整数，表示骑手能够获得的最大收入。
第二行输出用空格分隔的整数序列，表示从初始地点开始的配送路线。如果多条路线都能取得相同的最大收入，则输出地点编号序列字典序最小的那一条。

样例1

输入

1 2
5
1 2 3
1 2 4
2 3 5
1 3 2
3 4 10

输出

12
1 2 3

说明

从地点 1 出发，工作总时间为 2，因此最多可以完成 2 次配送。

两笔从 1 到 2 的订单收入分别为 3 和 4，合并后收入为 7。先配送 1 -> 2，再配送 2 -> 3，总收入为 $7+5=12$，路线为 [1,2,3]。

另一条可行路线是先配送 1 -> 3 再配送 3 -> 4，总收入为 $2+10=12$。两条路线最大收入相同，但 [1,2,3] 比 [1,3,4] 字典序更小，因此输出 [1,2,3]。

样例2

输入

5 0
3
5 2 10
5 3 20
2 3 5

输出

0
5

说明

工作总时间为 0，骑手无法完成任何配送。

即使初始地点 5 存在可选的订单，剩余工作时间等于 0 时配送过程立即结束，因此最大收入为 0，路线只包含初始地点 5。

样例3

输入

2 4
17
1 8 13
3 5 6
2 4 6
3 6 16
7 8 5
5 7 3
2 3 4
2 8 14
8 9 6
2 6 18
4 7 3
2 3 6
2 8 2
8 9 4
4 7 2
7 8 3
5 7 2

输出

29
2 3 5 7 8

说明

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写