#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
typedef long long ll;
const int N = 400005;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, nn;
struct Edge
{
    int to, nxt, col, wei;
} E[N];
int head[N], tot = 1;
inline void add(int f, int t, int c, int w)
{
    E[++tot] = {t, head[f], c, w}, head[f] = tot;
    return;
}
std::vector<std::pair<int, ll>> G[N];
int stt[N], len[N];
ll dis[N];
ll dijkstra(void)
{
    std::priority_queue<std::pair<ll, int>, std::vector<std::pair<ll, int>>, std::greater<std::pair<ll, int>>> que;
    memset(dis, 0x3f, sizeof(dis)), dis[1] = 0;
    que.push({0, 1});
    while(!que.empty())
    {
        auto tmp = que.top();
        que.pop();
        int x = tmp.second;
        ll d = tmp.first;
        if(d != dis[x])
            continue;
        for (auto pr : G[x])
        {
            int y = pr.first;
            ll w = pr.second;
            if(dis[y] > dis[x] + w)
                que.push({dis[y] = dis[x] + w, y});
        }
    }
    if(dis[stt[n]] == inf)
        return -1;
    return dis[stt[n]];
}
int main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, c, w; i <= m; ++i)
        scanf("%d%d%d%d", &u, &v, &c, &w), add(u, v, c, w), add(v, u, c, w);
    nn = 0;
    for (int x = 1; x <= n; ++x)
    {
        static int bac[N];
        int top = 0;
        for (int i = head[x]; i; i = E[i].nxt)
        {
            int c = E[i].col;
            bac[++top] = c;
        }
        std::sort(bac + 1, bac + 1 + top), top = std::unique(bac + 1, bac + 1 + top) - bac - 1;
        stt[x] = ++nn, nn += (len[x] = top);
    }
    for (int x = 1; x <= n; ++x)
    {
        static int bac[N], id[N];
        int top = 0;
        static ll tmp[N];
        for (int i = head[x]; i; i = E[i].nxt)
        {
            int w = E[i].wei, c = E[i].col;
            tmp[c] += w;
            bac[++top] = c;
        }
        std::sort(bac + 1, bac + 1 + top), top = std::unique(bac + 1, bac + 1 + top) - bac - 1;
        for (int i = 1; i <= top; ++i)
            id[bac[i]] = i;
        for (int i = head[x]; i; i = E[i].nxt)
        {
            int y = E[i].to, w = E[i].wei, c = E[i].col;
            G[stt[x]].push_back({stt[y], std::min((ll)w, tmp[c] - w)});
            G[stt[x] + id[c]].push_back({stt[y], tmp[c] - w});
            G[stt[y]].push_back({stt[x] + id[c], 0});
        }
        for (int i = 1; i <= top; ++i)
            id[bac[i]] = 0;
        for (int i = head[x]; i; i = E[i].nxt)
        {
            int w = E[i].wei, c = E[i].col;
            tmp[c] -= w;
        }
    }
    printf("%lld\n", dijkstra());
    return 0;
}