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<>();
        ArrayList<City> newCities = new ArrayList<>();
        
        for (int i = 1; i <= cityAmount; i++) {
            cities.add(new City(i));
            newCities.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()));
        }
        for (int i = 0; i < cityAmount; i++) {
            for (Flight flight : cities.get(i).neighbours) {
                for (Flight flight2 : flight.target.neighbours) {
                    if (i!=flight2.target.name-1) {
                        newCities.get(i).neighbours.add(new Flight (flight2.target,flight.cost));
                    }
                }
            }
        }
        flightCosts(newCities.get(0));
        io.print(cities.get(cityAmount-1).minDistance);
        io.close();
    }
    
    public static void flightCosts(City source) {
        source.minDistance = 0;
        LinkedList<City> cityList = new LinkedList<>();
        //source.flightsTo = 0;
	cityList.add(source);
        
	while (!cityList.isEmpty()) {
	    City c = cityList.poll();
            for (Flight flight : c.neighbours) {
               /* long cost = 0;
                if (c.flightsTo % 2 == 0) {
                    cost = flight.cost;
                }*/
                long cost = flight.cost;
                long newCost = c.minDistance + cost;
		if (newCost < flight.target.minDistance) {
		    //cityList.remove(flight.target);
                    flight.target.minDistance = newCost;
                    //flight.target.flightsTo = c.flightsTo + 1;
		    cityList.add(flight.target);
		}
                System.out.println(c.name + "-" + c.minDistance);
            }
            
            
        }
    }
 
    
}
class City implements Comparable<City>{
    public final int name;
    public ArrayList<Flight> neighbours;
    public long minDistance = Long.MAX_VALUE;
    public int flightsTo;
    public City(int 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 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: WRONG ANSWER

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: WRONG ANSWER

Test 5

Group: 1

Verdict: WRONG ANSWER

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: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED