Braços encreuats P61492

Els membres dels equips de la UPC al SWERC estan fent cua per entrar al Louvre. De sobte, entre tanta cultura, sorgeix una discussió molt important: quina és la manera correcta d’encreuar els braços? Curiosament, totes les opinions són diferents, i tothom creu que la seva manera és la correcta. Per exemple, en Miquel, com a bon comunista, encreua els braços com ho feia Lenin, i vol que tothom ho faci també.

Però no tothom pot copiar la manera d’encreuar els braços de qualsevol persona: ha d’existir un vincle mutu molt potent. Tot vincle, però, té un esforç associat. Per exemple, si l’Eric i en Dean tenen un vincle amb esforç 10, en Dean i en Miquel en tenen un amb esforç 5, i l’Eric i en Miquel un amb esforç 10, existeixen tres maneres d’aconseguir que tothom copiï en Miquel: si en Dean copia en Miquel i després l’Eric copia en Dean, si tant en Dean com l’Eric copien en Miquel, o si l’Eric copia en Miquel i després en Dean copia l’Eric. La primera té un esforç total 15, la segona 15 i la tercera 20.

Suposeu que dues maneres de copiar en Miquel són diferents si els vincles que s’usen són diferents, independentment de l’ordre en què s’utilitzin. Podeu decidir si existeix una única manera amb esforç total mínim d’aconseguir que tothom encreui els braços com Lenin?

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre n de membres, el nombre m de vincles entre ells, i m triplets d’enters x, y, k que indiquen un vincle entre x i y amb esforç k. Els membres es numeren entre 0 i n−1. En Miquel és el 0. Suposeu 2 ≤ n ≤ 5 · 10⁴, n − 1 ≤ m ≤ 10⁵, que x i y són diferents, que no hi ha cap parell repetit, i 1 ≤ k ≤ 10⁵.

Sortida

Per a cada cas, si existeix més d’una manera de copiar en Miquel amb esforç mínim, escriviu “yes”. Atrament, escriviu “no”. Sempre existirà com a mínim una manera de copiar-lo.