import java.io.InputStream; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.function.IntUnaryOperator; import java.util.function.LongUnaryOperator; public class Main { public static void main(String[] args) throws Exception { ExtendedScanner sc = new ExtendedScanner(); FastPrintStream pw = new FastPrintStream(); solve(sc, pw); sc.close(); pw.flush(); pw.close(); } @SuppressWarnings("unchecked") public static void solve(ExtendedScanner sc, FastPrintStream pw) { int n = sc.nextInt(); int m = sc.nextInt(); Graph g = new Graph<>(n); HashMap[] ids = new HashMap[n]; for (int i = 0; i < n; i++) { ids[i] = new HashMap<>(); } SimpleEdge[] edges = new SimpleEdge[m]; long[] ds = new long[m]; for (int i = 0; i < m; i++) { int u = sc.nextInt() - 1; int v = sc.nextInt() - 1; long c = sc.nextLong(); long d = sc.nextLong(); SimpleEdge e = new SimpleEdge(u, v, c); g.addEdge(e); ids[u].put(v, i); ids[v].put(u, i); edges[i] = e; ds[i] = d; } Dijkstra dij = new Dijkstra<>(g, 0); long s = dij.distance(n - 1); var path = dij.path(n - 1); Collections.sort(path, (e1, e2) -> toID(e1, ids) - toID(e2, ids)); int k = path.size(); int idx = 0; int id = toID(path.get(idx), ids); Graph h = new Graph<>(n); for (int i = 0; i < m; i++) { if (i == id) { int u = edges[i].from, v = edges[i].to; h.addEdge(new SimpleEdge(u, v, ds[i])); if (++idx < k) { id = toID(path.get(idx), ids); } } else { h.addEdge(edges[i]); } } long ans = s + new Dijkstra<>(h, n - 1).distance(0); pw.println(ans); } static int toID (SimpleEdge e, HashMap[] ids) { return ids[e.from].get(e.to); } } /** * @author https://atcoder.jp/users/suisen */ class FastScanner implements AutoCloseable { private final ByteBuffer tokenBuf = new ByteBuffer(); private final java.io.InputStream in; private final byte[] rawBuf = new byte[1 << 14]; private int ptr = 0; private int buflen = 0; public FastScanner(java.io.InputStream in) { this.in = in; } public FastScanner() { this(new java.io.FileInputStream(java.io.FileDescriptor.in)); } private final int readByte() { if (ptr < buflen) return rawBuf[ptr++]; ptr = 0; try { buflen = in.read(rawBuf); if (buflen > 0) { return rawBuf[ptr++]; } else { throw new java.io.EOFException(); } } catch (java.io.IOException e) { throw new java.io.UncheckedIOException(e); } } private final int readByteUnsafe() { if (ptr < buflen) return rawBuf[ptr++]; ptr = 0; try { buflen = in.read(rawBuf); if (buflen > 0) { return rawBuf[ptr++]; } else { return -1; } } catch (java.io.IOException e) { throw new java.io.UncheckedIOException(e); } } private final int skipUnprintableChars() { int b = readByte(); while (b <= 32 || b >= 127) b = readByte(); return b; } private final void loadToken() { tokenBuf.clear(); for (int b = skipUnprintableChars(); 32 < b && b < 127; b = readByteUnsafe()) { tokenBuf.append(b); } } public final boolean hasNext() { for (int b = readByteUnsafe(); b <= 32 || b >= 127; b = readByteUnsafe()) { if (b == -1) return false; } --ptr; return true; } public final String next() { loadToken(); return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size()); } public final String nextLine() { tokenBuf.clear(); for (int b = readByte(); b != '\n'; b = readByteUnsafe()) { if (b == -1) break; tokenBuf.append(b); } return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size()); } public final char nextChar() { return (char) skipUnprintableChars(); } public final char[] nextChars() { loadToken(); return tokenBuf.toCharArray(); } public final long nextLong() { long n = 0; boolean isNegative = false; int b = skipUnprintableChars(); if (b == '-') { isNegative = true; b = readByteUnsafe(); } if (b < '0' || '9' < b) throw new NumberFormatException(); while ('0' <= b && b <= '9') { // -9223372036854775808 - 9223372036854775807 if (n >= 922337203685477580l) { if (n > 922337203685477580l) { throw new ArithmeticException("long overflow"); } if (isNegative) { if (b >= '9') { throw new ArithmeticException("long overflow"); } n = -n - (b + '0'); b = readByteUnsafe(); if ('0' <= b && b <= '9') { throw new ArithmeticException("long overflow"); } else if (b <= 32 || b >= 127) { return n; } else { throw new NumberFormatException(); } } else { if (b >= '8') { throw new ArithmeticException("long overflow"); } n = n * 10 + b - '0'; b = readByteUnsafe(); if ('0' <= b && b <= '9') { throw new ArithmeticException("long overflow"); } else if (b <= 32 || b >= 127) { return n; } else { throw new NumberFormatException(); } } } n = n * 10 + b - '0'; b = readByteUnsafe(); } if (b <= 32 || b >= 127) return isNegative ? -n : n; throw new NumberFormatException(); } public final int nextInt() { long value = nextLong(); if ((int) value != value) { throw new ArithmeticException("int overflow"); } return (int) value; } public final double nextDouble() { return Double.parseDouble(next()); } public final void close() { try { in.close(); } catch (java.io.IOException e) { throw new java.io.UncheckedIOException(e); } } private static final class ByteBuffer { private static final int DEFAULT_BUF_SIZE = 1 << 12; private byte[] buf; private int ptr = 0; private ByteBuffer(int capacity) { this.buf = new byte[capacity]; } private ByteBuffer() { this(DEFAULT_BUF_SIZE); } private ByteBuffer append(int b) { if (ptr == buf.length) { int newLength = buf.length << 1; byte[] newBuf = new byte[newLength]; System.arraycopy(buf, 0, newBuf, 0, buf.length); buf = newBuf; } buf[ptr++] = (byte) b; return this; } private char[] toCharArray() { char[] chs = new char[ptr]; for (int i = 0; i < ptr; i++) { chs[i] = (char) buf[i]; } return chs; } private byte[] getRawBuf() { return buf; } private int size() { return ptr; } private void clear() { ptr = 0; } } } /** * @author https://atcoder.jp/users/suisen */ final class ExtendedScanner extends FastScanner { public ExtendedScanner() {super();} public ExtendedScanner(InputStream in) {super(in);} public int[] ints(final int n) { final int[] a = new int[n]; Arrays.setAll(a, $ -> nextInt()); return a; } public int[] ints(final int n, final IntUnaryOperator f) { final int[] a = new int[n]; Arrays.setAll(a, $ -> f.applyAsInt(nextInt())); return a; } public int[][] ints(final int n, final int m) { final int[][] a = new int[n][]; Arrays.setAll(a, $ -> ints(m)); return a; } public int[][] ints(final int n, final int m, final IntUnaryOperator f) { final int[][] a = new int[n][]; Arrays.setAll(a, $ -> ints(m, f)); return a; } public long[] longs(final int n) { final long[] a = new long[n]; Arrays.setAll(a, $ -> nextLong()); return a; } public long[] longs(final int n, final LongUnaryOperator f) { final long[] a = new long[n]; Arrays.setAll(a, $ -> f.applyAsLong(nextLong())); return a; } public long[][] longs(final int n, final int m) { final long[][] a = new long[n][]; Arrays.setAll(a, $ -> longs(m)); return a; } public long[][] longs(final int n, final int m, final LongUnaryOperator f) { final long[][] a = new long[n][]; Arrays.setAll(a, $ -> longs(m, f)); return a; } public char[][] charArrays(final int n) { final char[][] c = new char[n][]; Arrays.setAll(c, $ -> nextChars()); return c; } public double[] doubles(final int n) { final double[] a = new double[n]; Arrays.setAll(a, $ -> nextDouble()); return a; } public double[][] doubles(final int n, final int m) { final double[][] a = new double[n][]; Arrays.setAll(a, $ -> doubles(m)); return a; } public String[] strings(final int n) { final String[] s = new String[n]; Arrays.setAll(s, $ -> next()); return s; } } /** * @verified * - https://judge.yosupo.jp/problem/shortest_path * * @param type of edge */ class Dijkstra { public static final long UNREACHABLE = Const.LINF; private static final class State implements Comparable { final int v; final long d; State(int v, long d) {this.v = v; this.d = d;} public int compareTo(State s) {return d == s.d ? v - s.v : d > s.d ? 1 : -1;} } private final int n; private final int s; private final long[] dist; private final java.util.ArrayList prev; public Dijkstra(AbstractGraph g, int s) { this.n = g.getV(); this.s = s; this.dist = new long[n]; this.prev = new java.util.ArrayList<>(n); for (int i = 0; i < n; i++) { prev.add(null); } solve(g); } private void solve(AbstractGraph g) { java.util.Arrays.fill(dist, UNREACHABLE); dist[s] = 0; java.util.PriorityQueue pq = new java.util.PriorityQueue<>(); pq.add(new State(s, 0l)); while (pq.size() > 0) { State st = pq.poll(); int u = st.v; if (st.d != dist[u]) continue; for (Edg e : g.getEdges(u)) { int v = e.to; long c = e.cost; if (e.cost < 0) throw new AssertionError("Negative cost."); if (dist[u] + c < dist[v]) { dist[v] = dist[u] + c; prev.set(v, e); pq.add(new State(v, dist[v])); } } } } public java.util.ArrayList path(int t) { if (dist[t] == UNREACHABLE) return null; java.util.ArrayList path = new java.util.ArrayList<>(); for (int v = t; v != s; v = prev.get(v).from) { path.add(prev.get(v)); } int m = path.size(); for (int l = 0, r = m - 1; l < r; l++, r--) { Edg tmp = path.get(l); path.set(l, path.get(r)); path.set(r, tmp); } return path; } public long[] distances() { return dist; } public long distance(int i) { return dist[i]; } public boolean isReachable(int t) { return dist[t] != UNREACHABLE; } } abstract class AbstractGraph { final int n; final java.util.ArrayList edges; final java.util.ArrayList> adj; public AbstractGraph(int n) { this.n = n; this.edges = new java.util.ArrayList<>(n); this.adj = new java.util.ArrayList<>(n); for (int i = 0; i < n; i++) { adj.add(new java.util.ArrayList<>()); } } public abstract void addEdge(Edg edge); public Edg getEdge(int u, int i) { return adj.get(u).get(i); } public java.util.ArrayList getEdges(int u) { return adj.get(u); } public java.util.ArrayList getEdges() { return edges; } public int deg(int u) { return adj.get(u).size(); } public int getV() { return n; } public int getE() { return edges.size(); } } /** * @author https://atcoder.jp/users/suisen */ class FastPrintStream implements AutoCloseable { private static final int INT_MAX_LEN = 11; private static final int LONG_MAX_LEN = 20; private int precision = 9; private static final int BUF_SIZE = 1 << 14; private static final int BUF_SIZE_MINUS_INT_MAX_LEN = BUF_SIZE - INT_MAX_LEN; private static final int BUF_SIZE_MINUS_LONG_MAX_LEN = BUF_SIZE - LONG_MAX_LEN; private final byte[] buf = new byte[BUF_SIZE]; private int ptr = 0; private final java.lang.reflect.Field strField; private final java.nio.charset.CharsetEncoder encoder; private final java.io.OutputStream out; public FastPrintStream(java.io.OutputStream out) { this.out = out; java.lang.reflect.Field f; try { f = java.lang.String.class.getDeclaredField("value"); f.setAccessible(true); } catch (NoSuchFieldException | SecurityException e) { f = null; } this.strField = f; this.encoder = java.nio.charset.StandardCharsets.US_ASCII.newEncoder(); } public FastPrintStream(java.io.File file) throws java.io.IOException { this(new java.io.FileOutputStream(file)); } public FastPrintStream(java.lang.String filename) throws java.io.IOException { this(new java.io.File(filename)); } public FastPrintStream() { this(new java.io.FileOutputStream(java.io.FileDescriptor.out)); } public FastPrintStream println() { if (ptr == BUF_SIZE) internalFlush(); buf[ptr++] = (byte) '\n'; return this; } public FastPrintStream println(java.lang.Object o) { return print(o).println(); } public FastPrintStream println(java.lang.String s) { return print(s).println(); } public FastPrintStream println(char[] s) { return print(s).println(); } public FastPrintStream println(char c) { return print(c).println(); } public FastPrintStream println(int x) { return print(x).println(); } public FastPrintStream println(long x) { return print(x).println(); } public FastPrintStream println(double d, int precision) { return print(d, precision).println(); } public FastPrintStream println(double d) { return print(d).println(); } private FastPrintStream print(byte[] bytes) { int n = bytes.length; if (ptr + n > BUF_SIZE) { internalFlush(); try { out.write(bytes); } catch (java.io.IOException e) { throw new java.io.UncheckedIOException(e); } } else { System.arraycopy(bytes, 0, buf, ptr, n); ptr += n; } return this; } public FastPrintStream print(java.lang.Object o) { return print(o.toString()); } public FastPrintStream print(java.lang.String s) { if (strField == null) { return print(s.getBytes()); } else { try { Object value = strField.get(s); if (value instanceof byte[]) { return print((byte[]) value); } else { return print((char[]) value); } } catch (IllegalAccessException e) { return print(s.getBytes()); } } } public FastPrintStream print(char[] s) { try { return print(encoder.encode(java.nio.CharBuffer.wrap(s)).array()); } catch (java.nio.charset.CharacterCodingException e) { byte[] bytes = new byte[s.length]; for (int i = 0; i < s.length; i++) { bytes[i] = (byte) s[i]; } return print(bytes); } } public FastPrintStream print(char c) { if (ptr == BUF_SIZE) internalFlush(); buf[ptr++] = (byte) c; return this; } public FastPrintStream print(int x) { if (ptr > BUF_SIZE_MINUS_INT_MAX_LEN) internalFlush(); if (-10 < x && x < 10) { if (x < 0) { buf[ptr++] = '-'; x = -x; } buf[ptr++] = (byte) ('0' + x); return this; } int d; if (x < 0) { if (x == Integer.MIN_VALUE) { buf[ptr++] = '-'; buf[ptr++] = '2'; buf[ptr++] = '1'; buf[ptr++] = '4'; buf[ptr++] = '7'; buf[ptr++] = '4'; buf[ptr++] = '8'; buf[ptr++] = '3'; buf[ptr++] = '6'; buf[ptr++] = '4'; buf[ptr++] = '8'; return this; } d = len(x = -x); buf[ptr++] = '-'; } else { d = len(x); } int j = ptr += d; while (x > 0) { buf[--j] = (byte) ('0' + (x % 10)); x /= 10; } return this; } public FastPrintStream print(long x) { if ((int) x == x) return print((int) x); if (ptr > BUF_SIZE_MINUS_LONG_MAX_LEN) internalFlush(); int d; if (x < 0) { if (x == Long.MIN_VALUE) { buf[ptr++] = '-'; buf[ptr++] = '9'; buf[ptr++] = '2'; buf[ptr++] = '2'; buf[ptr++] = '3'; buf[ptr++] = '3'; buf[ptr++] = '7'; buf[ptr++] = '2'; buf[ptr++] = '0'; buf[ptr++] = '3'; buf[ptr++] = '6'; buf[ptr++] = '8'; buf[ptr++] = '5'; buf[ptr++] = '4'; buf[ptr++] = '7'; buf[ptr++] = '7'; buf[ptr++] = '5'; buf[ptr++] = '8'; buf[ptr++] = '0'; buf[ptr++] = '8'; return this; } d = len(x = -x); buf[ptr++] = '-'; } else { d = len(x); } int j = ptr += d; while (x > 0) { buf[--j] = (byte) ('0' + (x % 10)); x /= 10; } return this; } public FastPrintStream print(double d, int precision) { if (d < 0) { print('-'); d = -d; } d += Math.pow(10, -precision) / 2; print((long) d).print('.'); d -= (long) d; for(int i = 0; i < precision; i++){ d *= 10; print((int) d); d -= (int) d; } return this; } public FastPrintStream print(double d) { return print(d, precision); } public void setPrecision(int precision) { this.precision = precision; } private void internalFlush() { try { out.write(buf, 0, ptr); ptr = 0; } catch (java.io.IOException e) { throw new java.io.UncheckedIOException(e); } } public void flush() { try { out.write(buf, 0, ptr); out.flush(); ptr = 0; } catch (java.io.IOException e) { throw new java.io.UncheckedIOException(e); } } public void close() { try { out.close(); } catch (java.io.IOException e) { throw new java.io.UncheckedIOException(e); } } private static int len(int x) { return x >= 1000000000 ? 10 : x >= 100000000 ? 9 : x >= 10000000 ? 8 : x >= 1000000 ? 7 : x >= 100000 ? 6 : x >= 10000 ? 5 : x >= 1000 ? 4 : x >= 100 ? 3 : x >= 10 ? 2 : 1; } private static int len(long x) { return x >= 1000000000000000000l ? 19 : x >= 100000000000000000l ? 18 : x >= 10000000000000000l ? 17 : x >= 1000000000000000l ? 16 : x >= 100000000000000l ? 15 : x >= 10000000000000l ? 14 : x >= 1000000000000l ? 13 : x >= 100000000000l ? 12 : x >= 10000000000l ? 11 : 10; } } final class SimpleEdge extends AbstractEdge { public SimpleEdge(int from, int to, long cost) { super(from, to, cost); } public SimpleEdge(int from, int to) { super(from, to); } @Override public SimpleEdge reverse() { return new SimpleEdge(to, from, cost); } } abstract class AbstractEdge implements Comparable { public final int from, to; public final long cost; public AbstractEdge(int from, int to, long cost) { this.from = from; this.to = to; this.cost = cost; } public AbstractEdge(int from, int to) { this(from, to, 1l); } public abstract AbstractEdge reverse(); public int compareTo(AbstractEdge o) { return Long.compare(cost, o.cost); } } /** * @author https://atcoder.jp/users/suisen */ class Graph extends AbstractGraph { public Graph(int n) { super(n); } @SuppressWarnings("unchecked") @Override public void addEdge(Edg edge) { Edg rev = (Edg) edge.reverse(); adj.get(edge.from).add(edge); adj.get(edge.to).add(rev); edges.add(edge); } } class Const { public static final long LINF = 1l << 59; public static final int IINF = (1 << 30) - 1; public static final double DINF = 1e150; public static final double SMALL = 1e-12; public static final double MEDIUM = 1e-9; public static final double LARGE = 1e-6; public static final long MOD1000000007 = 1000000007; public static final long MOD998244353 = 998244353 ; public static final long MOD754974721 = 754974721 ; public static final long MOD167772161 = 167772161 ; public static final long MOD469762049 = 469762049 ; public static final int[] dx8 = {1, 0, -1, 0, 1, -1, -1, 1}; public static final int[] dy8 = {0, 1, 0, -1, 1, 1, -1, -1}; public static final int[] dx4 = {1, 0, -1, 0}; public static final int[] dy4 = {0, 1, 0, -1}; }