Lennot

import java.util.*;

public class t4 {
    
    public static void main(String[] args) {
        IO io = new IO();
        long cityAmount = io.nextLong();
        long flights = io.nextLong();
        
        ArrayList<City> cities = new ArrayList<>();
        
        for (long i = 1; i <= cityAmount; i++) {
            cities.add(new City(i));
        }
        for (long 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((int) cityAmount-1).minDistance);
        io.close();
    }
    
    public static void flightCosts(City source) {
        source.minDistance = 0;
        Queue<City> cityList = new PriorityQueue<>();
        source.nextIsFree = false;
	cityList.add(source);
        
	while (!cityList.isEmpty()) {
	    City c = cityList.poll();
            for (Flight flight : c.neighbours) {
                City v = flight.target;
                long cost = 0;
                if (!c.nextIsFree) {
                    cost = flight.cost;
                }
                long newCost = c.minDistance + cost;
		if (newCost < v.minDistance) {
		    cityList.remove(v);
                    v.minDistance = newCost;
                    v.nextIsFree = !c.nextIsFree;
		    cityList.add(v);
		}
            }
            
        }
    }

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


class Flight {
    public final City target;
    public final long cost;
    public Flight(City target, long 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