{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"Las personas que organizan el TBP (Torneo Beauchefiano de Programación) han intercambiado accidentalmente el código del algoritmo de Dijkstra con la receta de las famosas galletas con chispas de chocolate de la abuela. \n\nComo resultado, todos los participantes tienen dificultades para implementar el algoritmo y en su lugar están creando deliciosas bandejas de galletas. Tu misión es ayudar a los participantes escribiendo un programa que implemente el algoritmo de Dijkstra. ¡Buena suerte!"}},{"title":"Entrada","value":{"format":"MD","content":"La primera línea contiene dos enteros $n$ y $m$ ($2 \\leq n \\leq 10^5, 0 \\leq m \\leq 10^5$), donde $n$ es la cantidad de nodos y $m$ la cantidad de aristas.\n\nLas siguientes $m$ líneas contienen una arista cada una en la forma $u_i, v_i, w_i$ ($1 \\leq a_i, b_i \\leq n, 1 \\leq w_i \\leq 10^6$), donde la arista corresponde a $(u_i, v_i)$ con peso $w_i$. Esta arista es bidireccional.\n\nEs posible que el grafo tenga loops ($u_i \u003d v_i$) y aristas paralelas."}},{"title":"Salida","value":{"format":"MD","content":"Imprime $-1$ si no hay camino entre el nodo $1$ y el nodo $n$.\n\nDe lo contrario, imprime una línea con los nodos del camino más corto entre $1$ y $n$ en orden. Si existen varios puedes imprimir cualquiera."}},{"title":"Ejemplo 1","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\u003eSalida\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 6\n1 2 2\n2 5 5\n2 3 4\n1 4 1\n4 3 3\n3 5 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 4 3 5 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Ejemplo 2","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\u003eSalida\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 1\n1 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}