小Q非常喜欢旅游，在这个阳光明媚的夏天，他来到了一个美丽的海滨城市QD，在那里度过短暂的一个月假期顺便庆祝一下RQNOJ诞生三周年，然后就要乖乖回到学校好好学习了。QD这座城市，一共有N个旅游景点，可以供游客前来参观，每个景点都是那么的美丽，以至于他不想错过。QD还是一个交通非常发达的城市，一共有M条单向通行的道路，连接着各个旅游景点，但是，出现了一个让人比较头疼的问题，那就是QD的道路比较拥挤，经常会出现堵车的情况。为了便于旅游，小Q已经搜集到每条道路的拥挤情况Ki，Ki值越大表示这条道路越拥挤，小Q自然希望选择不拥挤的道路通行。

现在问题来了，小Q定义了一种游览方法:选取一个没有被访问的景点，从这个景点开始依次游览至少一个当前还没有被游览过的景点，最后从最后一个被游览的景点回到起始景点(即形成了一个圈)，这代表着完成了一次游览。小Q希望通过若干次这种游览方法，把所有景点都游览一次。因为NOI小Q考囧了，之后连数都不会算了，所以请你帮小Q计算一下，所需要经过的道路的Ki之和，使所有和最小。

约定及数据规模:

对于30%的数据,N<=12

对于100%的数据,N<=100 M<=2*10^4,时限:1000ms,内存上限:256MB且保证数据有解。

样例说明:

小Q选择1号景点为第一次游览的起始景点，然后来到第2个景点，1-2这条道路拥挤值为1

从景点2又来到了3号景点,2-3这条道路拥挤值为2

从3号景点回到起始景点1，3-1这条道路拥挤值为3

第一次游览结束，已经浏览所有景点，所以不再执行第二次游览。

第1行有两个正整数N,M，用空格隔开。

第2~M+1行，每行有3个整数u,v,k，表示有一条从景点u出发到景点v且拥挤情况为k的单向通行道路。

输出共计1行。

第1行表示小Q游览这N个景点，所经过的道路的拥挤值之和的最小值。