Untitled

#include <bits/stdc++.h>
using namespace std;

#define Task "ROBOT1"
#define ll long long
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define F first
#define S second

typedef pair<ll, int> li;

const int N = 1e6 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;

template<class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) {
            x = y;
            return true;
        } else return false;
    }

template<class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) {
            x = y;
            return true;
        } else return false;
    }

int numNode, numEdge;
ll dist[N];

struct Edge {
    int dest, color, cost;
};

vector<Edge> adj[N];

void dijkstra() {
    priority_queue<li, vector<li>, greater<li>> pq;
    pq.push({0, 1});
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    while (!pq.empty()) {
        int u = pq.top().S, curDist = pq.top().F;
        pq.pop();
        if (curDist > dist[u]) continue;
        vector<int> sumCost(numEdge + 1, 0), cnt(numEdge + 1, 0);
        for (Edge e : adj[u]) sumCost[e.color] += e.cost, cnt[e.color]++;
        for (Edge e : adj[u]) {
            int v = e.dest, c = e.color, w = e.cost;
            ll addCost = (cnt[c] == 1 ? 0 : min(w, sumCost[c] - w));
            if (minimize(dist[v], dist[u] + addCost))
                pq.push({dist[v], v});
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(Task".INP", "r")) {
        freopen(Task".INP", "r", stdin);
        freopen(Task".OUT", "w", stdout);
    }

    cin >> numNode >> numEdge;
    FOR(i, 1, numEdge) {
        int u, v, c, w;
        cin >> u >> v >> c >> w;
        adj[u].push_back({v, c, w});
        adj[v].push_back({u, c, w});
    }

    dijkstra();
    cout << (dist[numNode] == dist[0] ? -1 : dist[numNode]);

    return 0;
}