최단 경로 알고리즘을 작성했는데 ㅠㅠ 제가 했던 테스트케이스가

5 7
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
3 5 1

5 7
1
2 3 1
3 4 1
4 5 1
2 4 1
2 5 1
3 5 1
5 3 1

3 6
2
1 2 1
2 1 1
2 3 1
3 2 1
1 3 1
3 1 1

7 12
1
1 2 1
2 1 1
1 3 1
3 1 1
2 4 1
4 2 1
2 5 1
5 2 1
3 6 1
6 3 1
3 7 1
7 3 1

7 24
2
1 2 2
2 1 2
1 3 2
3 1 2
2 4 2
4 2 2
2 5 2
5 2 2
3 6 2
6 3 2
3 7 2
7 3 2
1 2 1
2 1 1
1 3 1
3 1 1
2 4 1
4 2 1
2 5 1
5 2 1
3 6 1
6 3 1
3 7 1
7 3 1

7 24
3
1 2 2
2 1 2
1 3 2
3 1 2
2 4 2
4 2 2
2 5 2
5 2 2
3 6 2
6 3 2
3 7 2
7 3 2
1 2 1
2 1 1
1 3 1
3 1 1
2 4 1
4 2 1
2 5 1
5 2 1
3 6 1
6 3 1
3 7 1
7 3 1

7 7
1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 1 1

7 6
2
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1

7 9
2
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 1 1
1 5 1
5 1 1

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

9 24
1
1 2 1
2 1 1
2 3 1
3 2 1
1 3 1
3 1 1
3 4 1
4 3 1
3 7 1
7 3 1
4 7 1
7 4 1
4 5 1
5 4 1
5 6 1
6 5 1
4 6 1
6 4 1
7 8 1
8 7 1
7 9 1
9 7 1
8 9 1
9 8 1

이 것 말고도 3시간동안 정말 계속 찾았는데 ㅠㅠ 못찾겠어요... 아 답답해 죽겠네요..