spfa 求最短路

/*
思想：要想松弛后面的点，必须要更新过当前的点，如果这个点都没有更新过，那么更新后面的点也是无效的
*/
import java.io.*;
import java.util.*;
class Main {
    static int N = 100010;
    static int n, m, idx;
    static int[] h = new int[N], e = new int[N], ne = new int[N], w = new int[N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];  //判断这个点是否在队列中
    static int max = 0x3f3f3f3f;
    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static int spfa() {
        Arrays.fill(dist, max);
        dist[1] = 0;
        st[1] = true;
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        while (!q.isEmpty()) {
            int t = q.poll();
            st[t] = false;
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[t] + w[i]) {
                    dist[j] = dist[t] + w[i];
                    if (!st[j]) {
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }
        }
        return dist[n];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        Arrays.fill(h, -1);
        while (m-- > 0) {
            s = cin.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            add(a, b, c);
        }
        int t = spfa();
        if (t == max) System.out.println("impossible");
        else System.out.println(t);
    }
}