#include <bits/stdc++.h>
#define N 1000005
using namespace std;
typedef long long ll;

int n, m, tot;
int _u[N], _v[N], _c[N], _w[N];
int head[N], pre[N<<1], to[N<<1], sz; 
unordered_map<int, int> mp[100005];
ll dis[N], sum[N], val[N<<1];
bool vis[N];
priority_queue<pair<ll, int> > q;

inline void addedge(int u, int v, ll w) {
    pre[++sz] = head[u]; head[u] = sz; to[sz] = v; val[sz] = w;
}

int main() {
    scanf("%d %d", &n, &m);
    tot = n;
    for (int i = 1, u, v, c, w; i <= m; i++) {
        scanf("%d %d %d %d", &u, &v, &c, &w);
        _u[i] = u, _v[i] = v, _c[i] = c, _w[i] = w;
        if (!mp[u].count(c)) mp[u][c] = ++tot, addedge(u, tot, 0);
        if (!mp[v].count(c)) mp[v][c] = ++tot, addedge(v, tot, 0);
        sum[mp[u][c]] += w; sum[mp[v][c]] += w;
    }
    for (int i = 1, u, v, c, w; i <= m; i++) {
        u = _u[i], v = _v[i], c = _c[i], w = _w[i];
        addedge(u, v, w); addedge(v, u, w);
        addedge(u, mp[v][c], 0); addedge(v, mp[u][c], 0);
        addedge(mp[u][c], v, sum[mp[u][c]]-w); addedge(mp[v][c], u, sum[mp[v][c]]-w);
    }
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0; q.push(make_pair(0, 1));
    while (!q.empty()) {
        int x = q.top().second; q.pop();
        if (vis[x]) continue; else vis[x] = 1;
        for (int i = head[x]; i; i = pre[i]) {
            int y = to[i];
            if (dis[y] > dis[x]+val[i]) {
                dis[y] = dis[x] + val[i];
                q.push(make_pair(-dis[y], y));
            }
        }
    }
    printf("%lld\n", dis[n]);
    return 0;
}