存图弄了好久。。。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.PriorityQueue;


class Main {
    static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int MAX = 0x3f3f3f3f;
    static int m, n;
    static int[] len;
    static boolean[] used;
    static Graph[] g;

    public static void main(String[] args) throws IOException {

        n = in();
        m = in();
        g = new Graph[n + 1];
        while (m-- > 0) {
            int from = in();
            int to = in();
            int val = in();
            if (g[from] == null) {
                g[from] = new Graph(to, val);
            } else g[from].add(to, val);
        }
        System.out.println(dijkstra());
    }

    public static int dijkstra() {

        len = new int[n + 1];
        used = new boolean[n + 1];
        PriorityQueue<Pointer> tree = new PriorityQueue<>(n + 1);
        Arrays.fill(len, MAX);
        len[1] = 0;
        tree.add(new Pointer(1, 0));
        while (!tree.isEmpty()) {
            int t = tree.poll().idx;
            if (used[t]) continue;
            used[t] = true;
            Graph tmp = g[t];
            while (tmp != null) {
                int val = tmp.val + len[t];
                if (val < len[tmp.to]) {
                    len[tmp.to] = val;
                    tree.add(new Pointer(tmp.to, len[tmp.to]));
                }
                tmp = tmp.next;
            }
        }
        return len[n] == MAX ? -1 : len[n];
    }

    public static int in() throws IOException {
        sc.nextToken();
        return (int) sc.nval;
    }
}

class Graph {
    int to, val;
    Graph next, end;

    public Graph(int to, int val) {
        this.to = to;
        this.val = val;
        this.end = this;
    }

    public void add(int to, int val) {
        this.end.next = new Graph(to, val);
        this.end = this.end.next;
    }
}

class Pointer implements Comparable<Pointer> {
    int idx, len;

    public Pointer(int idx, int len) {
        this.idx = idx;
        this.len = len;
    }

    @Override
    public int compareTo(Pointer o) {
        return Integer.compare(this.len, o.len);
    }
}