A22641.请柬

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

在电视时代,没有多少人观看戏剧表演。 Malidinesia 古董喜剧演员意识到这一事实,他们想宣传剧院,尤其是古色古香的喜剧片。他们已经打印了请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站,他或她将留在那里一整天,邀请人们参与。

这里的公交系统是非常特殊的:共有 nn 个站点和 mm 个线路,所有的线路都是单向的,连接两个站点。公共汽车离开起始点,到达目的地之后又空车返回起始点。

学生每天早上从总部所在的 11 号站点出发,乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候,所有的学生都回到总部。现在需要知道的是,学生所需的公交费用的总和最小是多少。

输入格式

输入的第一行是两个整数,代表站点个数 nn 和线路条数 mm

22 到第 (m+1)(m + 1) 行,每行三个整数 u,v,wu, v, w,代表存在一条从 uu 出发到达 vv 的线路,费用为 ww

输出格式

输出一行一个整数,表示最小费用。

输入输出样例

  • 输入#1

    4 6
    1 2 10
    2 1 60
    1 3 20
    3 4 10
    2 4 5
    4 1 50

    输出#1

    210 

说明/提示

数据规模与约定

对于 100%100\% 的数据,保证:

  • 1n,m1061 \leq n, m \leq 10^6
  • 1u,vn1 \leq u, v \leq n1w1091 \leq w \leq 10^9
  • 11 出发可以到达所有的站点。
首页