5490: 通道

11328 年，C 国的科学家们研发了一种高速传送通道，可以在很短的时间内把居民从通道的一端送往另一端，这些通道都是双向的。

美中不足的是，这种传送通道需要进行大量的维护和检修。经过规划，C 国总统决定在 M 城中新建这种通道，在 M 城中，建立了n个传送站和 3x(n-1)条传送通道，这些传送通道被分为 3 组，每一组都包含了(n-1)条通道。

当任意一组通道运行时，居民都可以通过这组通道从任意一个传送站前往任意的另一个传送站。也就是说，所有的传送站都会被通道所连通。

三组通道按照 1、2、3 的顺序轮流运行，循环反复。在任意一个时刻，都有且只有一组传送通道可以使用。形式化地，在第i天中，有且只有第((i-1)nod 3+1)组通道运行。

C 国著名科学家 Access Globe 正在进行一项社会调查实验：调查两个传送站之间的传送通道使用者的信息。Access Globe 的计划是这样的：

• 选定两个传送站 a、b
• 第一天，他从 a 出发，使用正在运行的这组通道沿最短路径到达b ，并调查经过的所有通道上使用者的信息
• 第二天，他从  b出发，使用正在运行的这组通道沿最短路径到达a ，并调查经过的所有通道上使用者的信息
• 第三天，他从 a 出发，使用正在运行的这组通道沿最短路径到达 b，并调查经过的所有通道上使用者的信息

Access Globe 知道每一条传输线路在运行时的使用者人数。他希望找出一对a 、b，使得在整个实验过程中所有经过的通道的使用者数量之和最大。Access Globe 希望参加 CCF NOI 2018 冬令营的你帮他解决这个简单的小问题。如果你成功地解决了这个问题，Access Globe 会送你一份小礼物——100 分！

从标准输入读入数据。

输入文件的第1行包含一个正整数n，表示传送站的个数，传送站从1到n编号；

输入文件的第2到第n行，每行包含3个数u,v,w，表示第一组通道中有一条连接u,v的通道，其运行时使用者数量为w人；

输入文件的第(n+1)到第(2n-1)行，每行包含3个数u,v,w，表示第二组通道中有一条连接u,v的通道，其运行时使用者数量为w人；

输入文件的第2n到第(3n-2)行，每行包含3个数u,v,w，表示第三组通道中有一条连接u,v的通道，其运行时使用者数量为w人。

输出到标准输出。

输出文件共 1行，包含一个整数，表示最大的使用者数量之和。

5
1 2 2
1 3 0
1 4 1
4 5 7
1 2 0
2 3 1
2 4 1
2 5 3
1 5 2
2 3 8
3 4 5
4 5 1

27