What edge case am I missing for Dijkstra's algorithm?

This is my Dijkstra's implementation. It's passing all cases in the pytest input.n.txt files but when I submit to the grading software (that doesn't provide the test or any output) I get an invalid result.

Here's my solution (passes all provided test cases, but not hidden ones).

# Uses python3

import queue
import sys
from math import inf


def dijkstra(adj, cost, s, t):

    seen = set([s])

    dist = [inf] * len(adj)
    dist[s] = 0

    prev = [None] * len(adj)
    prev[s] = s

    q = queue.Queue()
    q.put(s)

    while not q.empty():

        n = q.get()
        # print(n)

        edges = []
        for i, adjacent in enumerate(adj[n]):
            edges.append([adjacent, cost[n][i]])

        for i, edge in enumerate(edges):
            d = dist[n] + edge[1]
            if d < dist[edge[0]]:
                dist[edge[0]] = d
                edge[1] = d
                prev[edge[0]] = n

        edges = sorted(edges, key=lambda x: x[1])
        for (e, w) in edges:
            if not e in seen:
                seen.add(e)
                q.put(e)

        # print(dist)

    # print(prev)

    return dist[t] if dist[t] is not inf else -1


def parse(input):
    data = list(map(int, input.split()))
    n, m = data[0:2]
    data = data[2:]
    edges = list(zip(zip(data[0 : (3 * m) : 3], data[1 : (3 * m) : 3]), data[2 : (3 * m) : 3]))
    data = data[3 * m :]
    adj = [[] for _ in range(n)]
    cost = [[] for _ in range(n)]
    for ((a, b), w) in edges:
        adj[a - 1].append(b - 1)
        cost[a - 1].append(w)
    s, t = data[0] - 1, data[1] - 1
    return dijkstra(adj, cost, s, t)


if __name__ == "__main__":
    input = sys.stdin.read()
    print(parse(input))


def test_parse():
    assert 3 == parse(open("input.txt").read())
    assert 6 == parse(open("input.1.txt").read())
    assert -1 == parse(open("input.2.txt").read())
    assert 3 == parse(open("input.3.txt").read())
    assert 0 == parse(open("input.4.txt").read())
    assert 0 == parse(open("input.5.txt").read())

The format of the input is as follows...

number_of_vertices number_of_edges
from to weight
from to weight
start end

input.txt

input.1.txt

input.2.txt

input.3.txt

input.4.txt

input.5.txt

My program passes ALL of these. And I've tried messing around with all the edge cases I can think of testing but still it fails with a "Wrong answer" error in the testing software.

One of the comments of the thread of somebody who DID solve it:

Wow! I really struggled to put this one together, not because I didn't understand the Dijkstra algorithm but because of the difficulty in adjusting the priority of an item already added to a Python PriorityQueue class (whose use was implied by importing queue in the start code) or by keeping track of its position in the priority queue, which made translating the algorithm, as presented in the lectures, verbatim difficult.

In case it is helpful to others, the way I got around this was to move from thinking in terms of inserting vertices to the priority queue to inserting references to the vertices, with most updated distance at the time of insertion as the priority, instead. That way we don't need to adjust the priority of an item already added to the queue at a later time.

We may end up inserting several references to the same vertex to the queue, but we will, of course, encounter the reference with the least distance first, and we can ignore any future references to the same vertex that we might encounter afterwards. Further, we can abort the algorithm as soon as we've popped a reference to the destination vertex.

This still runs pretty efficiently (for me, a maximum time of about a twentieth of that allowed), and is, in retrospect, a small adjustment in viewing the problem.

Solution

Your algorithm uses a queue; Dijkstra's algorithm does not use a queue.

At each iteration you must select the unconfirmed vertex with the shortest path distance. This can be done using a min-priority queue, where the path distance is the priority, but note also that each vertex may have to be added to the priority queue more than once if it is discovered via different paths of different distances. (Your classmate initially tried to do this the hard way - by updating the priority of a vertex already in the priority queue, instead of just allowing each vertex to be present in the priority queue multiple times.)

So your algorithm is not a proper implementation of Dijkstra's algorithm, because it confirms the vertices in the order they are discovered, rather than in order of path distance from the source vertex.