{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"Há alguns anos, a iluminação de todas as vias e estacionamentos do campus da UFV foi substituída por um sistema com lâmpadas de led. Segundo comunicado da PAD no Institucional UFV, além da redução do consumo de energia elétrica e consequente economia em contas de luz da universidade, a substituição proporciona uma melhor qualidade de vida no campus. As lâmpadas de led emitem luz direcionada, reduzindo a sensação de desconforto dos olhos e ofuscação da visão de motoristas causadas pelas antigas lâmpadas de vapor de sódio, e ainda melhoram a percepção estética da paisagem: a antiga iluminação amarelada mascarava as cores do ambiente; já as de led realçam as tonalidades naturais das plantas, roupas, capivaras e pessoas.\n\nOs habitantes de Viçosa gostaram tanto da nova iluminação que exigiram da prefeitura que fizesse o mesmo na cidade. Após *\\#euqueroled* chegar ao topo dos *Trending Topics* do *Twitter*, o prefeito resolveu atender a população. Parcialmente! Para economizar, não vai substituir a iluminação na cidade toda. Claro que, a longo prazo, a substituição total traria economia, mas isto seria sentido apenas em mandatos de futuros prefeitos, então a questão agora é economizar com a instalação da iluminação. Em vez de instalar na cidade toda (custo total de \u003cspan\u003e$\u003c/span\u003e1 por metro de rua), vai instalar em apenas alguns trechos (custo de \u003cspan\u003e$\u003c/span\u003e1 por metro instalado). Entretanto, para evitar mais protestos, é necessário que de qualquer esquina seja possível chegar em qualquer outra usando apenas trechos de rua iluminados pelas novas lâmpadas de led."}},{"title":"Entrada","value":{"format":"MD","content":"A entrada contém vários casos de teste, cada um iniciado por uma linha contendo dois inteiros $N$ e $M$, respectivamente o número de esquinas e trechos de ruas de Viçosa ($1 \\leq N \\leq 200000$ e $N-1 \\leq M \\leq 200000$). Em seguida $M$ triplas de inteiros $X$, $Y$, $Z$, indicando que existe um trecho de rua de mão dupla que liga as esquinas $X$ e $Y$ com distância de $Z$ metros ($0 \\leq X, Y \u003c N$ e $X \\neq Y$). O grafo de cada caso de teste é conexo e o comprimento total de todos os trechos de rua é menor que $2^{31}$.\nA entrada termina quando $N \u003d M \u003d 0$."}},{"title":"Saída","value":{"format":"MD","content":"Para cada caso de teste escreva uma linha com a máxima economia que a prefeitura pode obter."}},{"title":"Exemplo","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eEntrada\u003c/th\u003e\n \u003cth\u003eSaída\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\n7 11\n0 1 7\n0 3 5\n1 2 8\n1 3 9\n1 4 7\n2 4 5\n3 4 15\n3 5 6\n4 5 8\n4 6 9\n5 6 11\n0 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\n\n51\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}