#include <bits/stdc++.h>

#define N 220000

#define INF 1000000000

using namespace std;

int n, m;

int ai[N], bi[N], ci[N], di[N];

int check;

class DIJ

{

private:

    struct node {int t, d;};

    struct comp {int operator () (node a, node b) {return a.d > b.d;}};

    priority_queue <node, vector <node>, comp> Q;

public:

    vector <int> bi[N], ci[N];

    int dis[N], vis[N], pre[N];

    int tot;

    void build(int a, int b, int c)

    {

        bi[a].push_back(b); ci[a].push_back(c);

        //if (check) printf("%d %d %d\n",a,b,c);

    }

    void solve()

    {

        for (int i = ; i <= tot; ++ i) dis[i] = INF, vis[i] = ;

        dis[] = vis[] = ;

        Q.push((node){, });

        while (!Q.empty())

        {

            int hd;

            do hd = Q.top().t, Q.pop();

            while (vis[hd] && !Q.empty());

            if (vis[hd]) break; else vis[hd] = ;

            for (int j = ; j < bi[hd].size(); ++ j)

                if (dis[hd] + ci[hd][j] < dis[bi[hd][j]])

                {

                    dis[bi[hd][j]] = dis[hd] + ci[hd][j];

                    pre[bi[hd][j]] = hd == ? bi[hd][j]: pre[hd];

                    Q.push((node){bi[hd][j], dis[bi[hd][j]]});

                }

        }

    }

} A, B;

int tot, ans = INF, bac = INF, pp;

int main()

{

    scanf("%d%d", &n, &m); A.tot = n; B.tot = n + ;

    for (int i = ; i <= m; ++ i)

    {

        int a, b, c, d;

        scanf("%d%d%d%d", &a, &b, &c, &d);

        tot ++; ai[tot] = a; bi[tot] = b; ci[tot] = c;

        tot ++; ai[tot] = b; bi[tot] = a; ci[tot] = d;

        A.build(a, b, c);

        A.build(b, a, d);

        if (a ==  || b == ) if (bac > c + d) bac = c + d, pp = (a == ? b: a);

    }

    A.solve();

    A.dis[] = bac; A.pre[] = pp;

    check = ;

    for (int i = ; i <= tot; ++ i)

    {

        if (ai[i] == )

        {

            if (A.pre[bi[i]] != bi[i])

                B.build(, bi[i], ci[i]);

        }

        else if (bi[i] == )

        {

            if (A.pre[ai[i]] != ai[i])

                B.build(, n + , A.dis[ai[i]] + ci[i]);

            else B.build(ai[i], n + , ci[i]);

        }

        else if (A.pre[ai[i]] != A.pre[bi[i]])

            B.build(, bi[i], A.dis[ai[i]] + ci[i]);

        else B.build(ai[i], bi[i], ci[i]);

    }

    B.solve();

    printf("%d\n", B.dis[n + ]);

}