[Opoi 2024] 数据转换

题目背景

![](data:image/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDAAsJCQcJCQcJCQkJCwkJCQkJCQsJCwsMCwsLDA0QDBEODQ4MEhkSJRodJR0ZHxwpKRYlNzU2GioyPi0pMBk7IRP/2wBDAQcICAsJCxULCxUsHRkdLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCz/wAARCAC0AKsDASIAAhEBAxEB/8QAHAAAAQQDAQAAAAAAAAAAAAAAAAEEBgcCAwUI/8QAPBAAAgEDAgQEBAIGCgMAAAAAAQIDAAQRBSEGEjFBE1FhcSKBkaEUMgcjQlKx0RUkQ1NicpLB8PFjgqL/xAAYAQEBAQEBAAAAAAAAAAAAAAAAAQIDBP/EAB0RAQEAAgMBAQEAAAAAAAAAAAABAhEhMUESA1H/2gAMAwEAAhEDEQA/ALY3pDS4oxUGplzXPvLKOdGVlyCCK6pFYMuRQVFxLwasniTW6Ybc4AquJ4LzTpuWRWGDscHBr0xcWySKwIFQniDhi2u0kIjGTnoKCCcN8VXulzo8Uh5TgSRk/C49qunROINO1uAPbvyzKB4sLH41PmPSvPWqaPeaVMxCsYg2zYO3vTrR9cu7KaOSCZoplIwwOPlQek80VFeGuK7bWI0guGSO9AHfAl9h51KqBaKKKAzRRRQJS0UUBRRRQFFFFAUUUUCUUZooCkxS0UGtlBprNArgginprBgKCGaxokNykmYwcg5yNjVTa7w3c6fJJcWysYQSWUdU9R6V6DmhDA7VHtR0xJQ/wjv260FHadqk1vIhDsroQVYEggirj4W41ivhFZ6iyrNgLFcZ+F+wEnr61X3EPCboZLqwjwwy0kKjr6p/Kota309s4UllKt6ggig9TAgjIOe9FVJoX6Q5bG1MN7EbtEjzCRII2THZ3bO1day/SZDJJD+L01/w0rY8WxZpmjHmyEAke1BY1Fa4Z4LiGK4gkWSCVBJHIp+FkIzneswysAykMp3BUgg+xFAtFFFAUUUUBRRRQFFFFA1tLu2vbeG5tpFkhmUOjKe3kfUd6c1S3CfFU+lSrHITJp8zL48WSWjJ28WL1Hcd/erjgnhuIopoZEkilRZIpEOVdW3BBoN1FFFAUlLRQa2XNNZoQwO1PK1sOtBHL2xDZIXeq84m4Vhnjub62CxXEMck0oxhJVRSx9mq3JowQdq4t9ZxukqOuUkV43HmrAqRQeeFk3UPkxruV7MR0zXTtLyQyr4hCxMvIkagBFHYttW7iHh680W4bKl7SWTFvMBsQRnkbyYVygCERh5DmqiTrLcJALaOWUWwYv8AhxI/hc56sEzy5+VdbReJNX0R/wCqS89sWzJaz5aFj3wM5B9R96jFldhlWJz8Q2UnuPKn+N8j/uoq6dD4r0bW+SJH/DXxG9rORlj/AOJ+jfx9KkFed1O4IyCpBG+CCOhBFWBw1xw0fh2OuSFk2SG+bdk7BbjuR/i+vmCLIorFWV1V1ZWV1DKykFWUjIII2xWVAUUUUBRRRQeWrW4kgkMcmQVOCDsQRVl8F8TJYSLYXcmLC5cGJ2Pw207bZP8Agb9ryO/c1HOL+Hnt3a+t0/Kf1yqO37386j9hcZHIx9MHp7Vdj0ypBxWdVzwvxpp8FlHY6zcSI9vyx20/hyyh4MbLIUBOV6Zx0x5VP7a6tbyCK5tZopoJV5o5YWDIw6bEfeoN9JS0hoCsTisqSg0suaY3EfMDXQYVokXNBDdbsY7qGSGaNXiYZZWGRkbgj1Haqg1C3W0vby2XPLFKVXm68pAIzV+XcCuCMdqqXjPSJLS+N+gJguuVZB/dyqoXf0bGR86CGhijH93O3pXVtL3okjeXK3+xrlHqfekVipyvQdR8uooJLnODn2IpSeUZYgAdScAfU1ybe6YhYy7AE4yoBI7Y3/lT1VDnmSEyN1D3DHHuAcn7VVS7hrjW50do7WZZrvTMgGNBl7fJ3aFnIGPNc49j1t20u7S+t4bq1lSWCZeaN0Ox9COoI7ivOpbflecsT/Z2w+xIyfuK7fD2varoFwXtIlNrMwN3b3ErETAbcw5c4fyOffI2qIvaiudpOsadrNqt1ZSZAws0T4EsDn9mRR9j0NdGgWiiigimq2CXCOpUHmBUgjYg7YqidQjjs9T1G1tG/VxXU0au2DgIxUn+OK9HzpkE+W49xVF8RaNaWvEGrQKzGF3W6jVMqEEw5zESR+ySRt/09HIS5jaIW4Se6blw5QYG++7VM/0f6++k6l/R1148Om6jnBuW54oLsAckgkHQN+Vs+h7VGooYoVCRqFX0z9yazyaovmDWtCubhbS31OxmuWzyxwzo5bAyQpBwT6A10a88RSyxSRyxOySxOskboSHR1OVZSO47VPdN/SLcxIkeq2PjsuAbi1ZYnb1eJ/gz7MPaoLKpKY6XqthrNnFfWTsYXZ0ZZAFkjkQ4ZJFBOCPfuD0NPqDE1qYZrca1kUDKZMg1H9a0yG/tZ4JEDB1I9fcevlUndc0zmjzmg876np1zpt1LBMpwCfDfGzrnr7+dMB1Py/hVz8ScPw6hC5CfGBkEdQfMVUd9p9zYTPFKp6nlbGzAeVA1GQcjr/GnkFyo5VcFkBOVJOxPpTOgZBBXqfpQd78TbxqMMgUjYAAfYU3k1NF2jUsfNtvsKY2ttJeXcNqssMckzciNO/hRc5/KrOQQM9ATtv8AMTKw4Bm5j/Sdx4RU4aGHdgeu7Hapcpj21Jb0jllr2uWFzHeWF08E0fTk5eR16lJUxgqe4NeiNIvZNR0rR9QkRI5L7T7S7kRM8qPNEshC53xvtVZT8E6DJCIo/HtpgCFnRzIckYBdGPKR9PerG0OMWukaNZ+IkjWVhaWkjR55S8MSxkgNvg42qTKXouNjrUtYA0taZNJRs2SqjBLMxwqqBkknyFU1xFqtnrOpPdWYP4WKJLWCRwQ0yRlj4hB6A5OB5Y71c7Kr5jbdZAY2z3DjkP8AGvPAQ2l3d2TEERyyLGc7EKxXb6U9Un4lmx4VvK4/efljX3HNvj5Umb99s28QPTAaRv8A6wPtTnHl7/KkKhgFIzuNvWqG/wCHkfPi3EzjoVVgiZ9kxSeDHb4kiBCrtKoJPMh74Pcda2xlvjVHRuViMFdjv15h9+tZqyONiCcDmXIOM9jiglXBOuf0XqiWs0mLHVHjgck/DFck8sMvsc8je4/dq3815yReXngboBmPtmM7YyPLp9KufhDXTrGloJ35r+wKW14Sfil2/V3B/wA46+oNESasSKM0VBgwpu6ZzToitbLQc2aIHIIqI8QcPwX0UhCDmxnbrnzBFTh0zTSWIEHIoPPuo6bc2MzI6nlyeVugPofX+NMgOlXLrmhQXkUh5ASQcjHWqt1PS7jT5W5lYxk7Meo9GoGlkM31uM4Pix4PqCKuWyuwsccNxzGEKBHIoLSW/sBuU8x1Hb9009pkTyanZoqli0yYA8gck1a8IwAPQCuP6umDtGF/gGYeRlDxyFv1boejIy5yP+dq2RzPayq0MvPjZ8KVjb2Db/amFrO8R8Ir4lvIxJizysjn9uJjnB/eGMH33rVq2tafostnb3MUklxeRvNBHGVEYUOUBllfOCTnACHp9eWMt6btnqZWl3FcrldnH5kPUeo9Kd5FQWy1Fry3kuHha3mjdFtRaMzyLKVY55nIHL55wMdqm6Z5E5sFuVeYjYE43OK9EycrGh25Cp8mB+hzVAcRxPbaxqY5Sr22o3gx5oZmYfLer8lGc1VH6QrAx31vqKp8F2ggmIG3ixLgE+64/wBNa9RGkcSIki9CM/XtSODysAM59cZHlmmto5Rnt27fHGT3U08LIBuQPc1oa8MBGwTBX4eVcH4PKtgHpjO5Hr61pe7to85dflvTWTVIh+RSfegfSoWCMuBJG2Vz0IOxU+hH/Nq6+hau+h6nb3w5jbkeBfRruZLVyCSB5psy+2P2qiL6ncN+UBa1+NcyfnkfB7DYUHpyOSORUkjdXjkVXjdDlXRhzKykdiNxW0GolwFO83Cuhc7EtElzb5J35YbmVFHyGKlgqIyrEisxRig0staHTNOyKwZKDmSwgg7bVHNX0OK7R8IMkHtUwaPNamhBHQVBTk3Dd1a3CzQK6SRuGR0JBUjuKkljcTSKqXChZwMNgYV/Vf5VMp7KNwcqD8q5Fxpig8yrgjfasZTbUumiFSzqASCdgVxkH0yCPtXA4rgluL7TeYPJ4dlglsFsmeRtsY6dq7yq6MBIHKg8x5CwbC77cu9P5YrG7lSTwS5WNUXxD4cYAJOcAFu9c8ZY1ld9ORo8JexZ8A+DOuVOQXdk8NVXHU5OMevpVghhgZOD3HlXGtLSGN45Pg/V5aKKJAkSORjnI3JbGwJPeunzV0xmuWL/AASDY1G+ItMTVNPu7Ugc7rzQsf2Jk+JD9dj6GpO42phcJkEVtHny5SaMId454JGhcEbjqCCPQiue8lw7cpZmJ7Dv9Km/G+mmzvDdIuIb0q7EdBOuzD5jB+tcbhOa3t9fsZJ0Dp+sTlYAg8wKkEHbcZx64pvhXMtdF1i9I8C1mcHvyED6tipDY8A6tOf6zcWdoOUuRPL8fICASqqMnqO1WVqt3pOhwi6vHeO0Z0SJoIWl5jIvOgwuAMjuSK5ml8S6Jrd5Pa2kNwskEPjJLcLHiReYIwXkzgjbYtv8t+f3bGvlx7bgHS48GW8NyuSOeD4Y2Kkg8pIz6V0peDNBezlgW3aIsMxzqW5klx8JJOxHmK7l4Lx7W5jsphb3bRkW8xVWEb9RkMCMHodu9R/TdG4rjv7fUdW4hkuXhDgwIHkjdHGDHmQhQD6J2rO7fWtOzwNFNZ6GllOvLPZ6hqdvKN93Wctn55GKmCGuHZPySlDsspyNsESAY3PqB9vWu2g2FdZdxzs03rWVIgrKtITFIRWVFBqK1gUpxiseUVA2Mee1aJLcEHauhyigoKio/NY56CtUdpIpqQmMeVazCPKmjZnBEVG9OeX0raI8VnyVUIwzTaVOtPSK1Ouaoh/E2jJqun3Fucq/wyROACUdDkHB+YPvVUx6TeWOoQNJHIY45lLsqkELn8w9utX7JECDtXAvtOikLHkGfas1SWYg1LTmsrmKOY24VgkyLIjw5yuVYEfCenuKyiiiiURxxJGg25Y0VFGPILgUwhluNOEs0KB5baOQpG5IWVWHLytjfHQ/KuM11x7fzOY2itYeb4Vt4UiPLjqZGy+fnXn1y6y8JYUZVLvhEA/PKwRfL8zYFc661rQLJWefUYSVblKWoa4fOcYxGCv3rirwtqN24k1C/kkY/vu8zdc4zIf9qfpw7oNqB47hz3Ejjf8A9R/KunOtM/RjccbWCRSvY6deXDRhmJndLcLyn83KgZtuvWrIt3EsUMn95HG/+pQ1RGO00vw3jtLBZSyMowiIhyMfE0mNvlUosVeK2tInKl44Io3K/l5lUA8vpWsZpm3boL0rPtWCmsxXRktFFFAmKMUtFAmKMUtFBjikIrLFFBjilxS4paDGsSKzpDQaHWmcsQOdq6JUVqaPPapRGbyBkLOgHNgjB6H3rlXGrX0YwkMS422y38dvtUwmtQ4O1cefSY3YkjrWdKiUuoarcEgyyBTkYQlRv/lwPtWUFvduQcOfepTHpMCf2Yp7HZIuMKPpTQ5unQTpy8w2qRQKcDNa44AvQU8jTFaiNi1sFYqKzqgpaBRQFJS0UCUUtFAlFFFAUUtFAlFFFAlJWVGKDWVFaGiBPSnNJiga+EKyEYrfyilxQawnStgGKXFLQAFLRRQLRRRQFFJS0BRSUtAUUlFAtFFJQLgUUUVQUYoooDAo5RRRQGBSYFFFAuBRRRQFFFFAUUUUBRRRQFFFFAUUUUBRRRQf/9k=) ![](https://tse2-mm.cn.bing.net/th/id/OIP-C.ojcWO_62WQhtFFaZSdmbgAHaEo?w=244&h=180&c=7&r=0&o=5&pid=1.7) Arrda 家里面有很多五花八门的用电器和数据线,而且很多用电器的插头种类都不一样,这导致每次 Arrda 想要共享两个用电器的数据时都要一半天用来买到合适的数据线,而且有的时候数据线很贵! 于是 Arrda 想让你求出花钱最少的数据转换方案。

题目描述

Arrda 家中有 $n$ 类,$2n$ 种数据线接头,每一类插头有 $2$ 种不同接头,种类分别为 $i$ 和 $n+i$,**有且只有同一类的不同接头可以互相连接(你可以理解为 $i$ 是凸出的接头,$n + i$ 是凹的接头,可以连接可以理解为插上)**。 商城里售卖着 $m$ 种双向数据线,每根双向数据线两端各有一个接头,种类分别为为 $u_i,v_i$。同时,第 $i$ 种双向数据线有一个购买价格 $w_i$,每种数据线可以购买无限条。 Arrda 想要交换两个用电器的数据,其中两个用电器的接头种类编号为 $S,T$,求能使这两个用电器能直接或由若干条数据线相连的最小总价格(毕竟买数据线需要钱),如果无解,输出 `I have no idea how to solve it.`,注意,**两个用电器的接口不能直接连接数据线,因为它们在用电器上,而非数据线两端!**

输入输出格式

输入格式


第一行两个整数 $n,m$,意义见题面。 接下来 $m$ 行,每行三个整数 $u_i,v_i,w_i$。 接下来一行两个整数 $S,T$。

输出格式


一个非负整数表示能使这两个用电器能直接或由若干条数据线相连的最小总价格。 若无解,请输出 `I have no idea how to solve it.`。

输入输出样例

输入样例 #1

4 4
5 8 10
7 8 2
2 3 1
5 6 5
1 4

输出样例 #1

8

输入样例 #2

4 1
2 3 1
1 8

输出样例 #2

I have no idea how to solve it.

输入样例 #3

4 1
2 3 1
1 5

输出样例 #3

0

输入样例 #4

5 10
1 2 603124134
2 3 373980902
2 4 6578324
3 5 936364479
4 6 182080546
4 7 340293479
6 8 753053273
1 9 274129271
3 10 616764767
4 6 255802600
1 2

输出样例 #4

3673658542

说明

### 样例 1 解释: ![picture](https://cdn.luogu.com.cn/upload/image_hosting/4j95t4xl.png) ``` 1=5->6=2->3=7->8=4 ``` 可以证明,没有总代价更小的方案。 ### 样例 4 解释 ![222](https://cdn.luogu.com.cn/upload/image_hosting/k88cjz1t.png) ``` 1=6->8=3->5=10->3=8->6=1->9=4->7=2 ``` `4->6` 有两种数据线,我们选择代价为 $182080546$ 的那一根,因为其代价更小。 可以证明,没有总代价更小的方案。 ### 数据范围 对于 $100\%$ 的数据,$1\le n,m \le 10^5$,$1\le u_i,v_i,s,t \le 2 \times n$,$1\le w_i \le 10^9$。