该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

宋奕霏、崔馨月、武锦澄和曹智钦正在为校园科技节设计一座虚拟“寻宝乐园”。

宋奕霏画好了地图，崔馨月给通道标好了长度。她们发现，每个地点通往其他地点的通道数量都不一样。

武锦澄想到了一个办法：“给每个地点准备一份可以不断添加内容的通道清单！读到哪条通道，就把它记到对应起点的清单末尾。”

曹智钦点点头：“记录完成后，我要看看每个地点的清单，还要知道所有通道的长度加起来是多少。”

请你使用 vector 邻接表，帮他们完成这个通道记录本。

题目描述

寻宝乐园里有 $N$ 个地点，编号为 $1$ 至 $N$，以及 $M$ 条带长度的单向通道。

每条通道用三个整数 $u,v,w$ 表示：从地点 $u$ 出发，到达地点 $v$，长度为 $w$。

你需要完成两件事：

1. 计算所有通道的长度之和。
2. 按地点编号 $1,2,\ldots,N$ 的顺序，输出每个地点的出发通道清单。每份清单中，通道的顺序必须与它们在输入中出现的顺序一致。

通道只能按照给定方向通行，$u\to v$ 不代表存在 $v\to u$。

同一对地点之间可能有多条同方向通道。每一条都要单独保存、单独输出，其长度也要单独计入总和。

输入格式

第一行包含两个整数 $N,M$，分别表示地点数量和通道数量。

接下来 $M$ 行，每行包含三个整数 $u,v,w$，表示一条起点为 $u$、终点为 $v$、长度为 $w$ 的单向通道。

通道的输入顺序不保证按起点或终点排序。

输出格式

共输出 $N+1$ 行。

第一行输出一个整数，表示所有 $M$ 条通道的长度之和。

接下来 $N$ 行，按地点编号从小到大输出清单。地点 $u$ 的清单占一行，格式为：

u k v1 w1 v2 w2 ... vk wk

其中：

• $u$ 是起点编号。
• $k$ 是以 $u$ 为起点的通道数量。
• 每一组 $v_i,w_i$ 分别表示一条通道的终点和长度。
• 这些通道必须按照它们在输入中出现的先后顺序输出，不要按终点编号排序。

如果地点 $u$ 没有出发通道，只输出：

u 0

同一行内的整数之间用空格分隔，不要输出其他提示文字。

样例 1

4 5
1 3 5
2 4 6
1 2 7
3 1 4
1 3 2

24
1 3 3 5 2 7 3 2
2 1 4 6
3 1 1 4
4 0

样例 1 解释

所有通道的长度之和为 $5+6+7+4+2=24$。

以地点 $1$ 为起点的通道，按输入顺序依次是：

所以地点 $1$ 的清单是 1 3 3 5 2 7 3 2。虽然有两条通道都通向地点 $3$，但它们需要分别记录。

地点 $4$ 没有出发通道，所以仍要输出一行 4 0。

样例 2

3 0

0
1 0
2 0
3 0

样例 2 解释

地图上没有通道，总长度为 $0$，每个地点的清单都是空的。

数据范围

对于所有测试数据：

• $1\le N\le1000$。
• $0\le M\le10000$。
• $1\le u,v\le N$，且 $u\ne v$。
• $1\le w\le1000000000$。
• 同一对地点之间允许有多条同方向通道。

所有通道的长度之和可能超过 int 的范围，请使用 long long 保存总和。

学习提示

为每个地点建立一个 vector，每个元素保存一条出发通道的终点和长度。读入一条通道时，用 push_back 添加到起点对应的 vector 末尾；输出时按保存顺序遍历即可。

运行限制

• 时间限制：$1$ 秒。
• 内存限制：$256$ MiB。
• 使用标准输入、标准输出。