Lennot

import java.util.*;

public class t4 {
    
    public static void main(String[] args) {
        
        IO io = new IO();
        int cityAmount = io.nextInt();
        int flights = io.nextInt();
        
        ArrayList<City> cities = new ArrayList<>();
        
        for (int i = 1; i <= cityAmount; i++) {
            cities.add(new City(i));
        }
        for (int i = 0; i < flights; i++) {
            cities.get(io.nextInt()-1).neighbours.add(new Flight(cities.get(io.nextInt()-1),io.nextInt()));
        }
        flightCosts(cities.get(0));
        io.print(cities.get(cityAmount-1).minDistance);
        io.close();
    }
    
    public static void flightCosts(City source) {
        //Boolean isFree = false;
        source.minDistance = 0;
        PriorityQueue<City> cityList = new PriorityQueue<City>();
	cityList.add(source);

	while (!cityList.isEmpty()) {
	    City c = cityList.poll();
            //check the logic of when the flight is free, currently every second polled one is free
            //this behaviour is incorrect
            for (Flight flight : c.neighbours) {
                City v = flight.target;
                int cost = 0;
                if (c.flights % 2 == 1) {
                    cost = flight.cost;
                }
                int newCost = c.minDistance + cost;
		if (newCost < v.minDistance) {
		    cityList.remove(v);
                    v.minDistance = newCost;
                    v.flights = c.flights + 1;
		    cityList.add(v);
		}
            }
           // isFree = !isFree;
            
        }
    }

    
}
class City implements Comparable<City>{
    public final int name;
    public ArrayList<Flight> neighbours;
    public int minDistance = Integer.MAX_VALUE;
    public int flights = 1;
    public City(int name) {
        this.name = name; 
        neighbours = new ArrayList<>();
    }
    public int compareTo(City other) {
        return Integer.compare(minDistance, other.minDistance);
    }
}


class Flight {
    public final City target;
    public final int cost;
    public Flight(City target, int cost) { 
        this.target = target; 
        this.cost = cost; 
    }
}

Test 1

Group: 1

Verdict: WRONG ANSWER

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: WRONG ANSWER

Test 7

Group: 2

Verdict: WRONG ANSWER

Test 8

Group: 2

Verdict: WRONG ANSWER

Test 9

Group: 2

Verdict: WRONG ANSWER

Test 10

Group: 2

Verdict: WRONG ANSWER

Test 11

Group: 3

Verdict: WRONG ANSWER

Test 12

Group: 3

Verdict: WRONG ANSWER

Test 13

Group: 3

Verdict: WRONG ANSWER

Test 14

Group: 3

Verdict: WRONG ANSWER

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED