Pentru a afla costul de la nodul $1$ la nodul $N$, vom utiliza 'algorimul lui Dijkstra':problema/dijkstra puţin modificat. Astfel, vom reţine pentru fiecare nod, valoarea minimă între nodul $1$ şi nodul respectiv. Când dorim să mergem în vecinii nodului curent trebuie verificat dacă $min(costul_nodului_curent, costul_muchiei) > costul_nodului_vecin$. Complexitatea acestui algoritm este $O(M logN)$.
*Soluţie 2*

Vom căuta binar răspunsul între 1 şi valoarea maximă pe care o poate avea o muchie. Pentru o valoare fixată, vom considera doar muchiile cu valoarea mai mare sau egală cu valoarea fixată şi vom utiliza o 'parcurgere în adâncime':problema/bfs pentru a vedea dacă nodurile $1$ şi $N$ sunt în aceeaşi componentă conexă. Complexitatea acestei soluţii este $O((N + M) * log MaxVal)$.

Vom căuta binar răspunsul între 1 şi valoarea maximă pe care o poate avea o muchie. Pentru o valoare fixată, vom considera doar muchiile cu valoarea mai mare sau egală cu valoarea fixată şi vom utiliza o 'parcurgere în adâncime':problema/bfs pentru a vedea dacă nodurile $1$ şi $N$ sunt în aceeaşi componentă conexă. Complexitatea acestei soluţii este $O((N + M)*log MaxVal)$.

*Soluţie 3*