#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define _rep(i, x, y) for(int i = (int)x; i < (int)y; ++i)
#define _dep(i,x,y) for(int i = (int)x; i > (int)y; i--)
#define PII pair<int,int>
#define eb emplace_back
#define pb push_back
#define fi first
#define se second
#define PQ priority_queue
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VII;
typedef vector<ll> VL;
typedef vector<vector<ll>> VLL;
constexpr int mod = 1e9 + 7;
constexpr int KINF = 0x3f3f3f3f;
constexpr double eps = 1e-7;
constexpr ll inf = 1e16;
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<tuple<int,int,int>>> g(n);
    _rep(i, 0, m){
        int t, a, b, c;
        cin >> t >> a >> b >> c;
        g[--a].eb(--b, t, c);
        g[b].eb(a, t, c);
    }   
    auto dij = [&](){
        PQ<pair<ll,int>> pq;// [len, u]
        VL d(n * 1000 + n, inf);
        d[0] = 0;
        pq.emplace(0, 0);
        while(!pq.empty()){
            auto [len, tmp] = pq.top();
            pq.pop();
            len = -len;
            if(len > d[tmp]) continue;
            int u = tmp % n, s = tmp / n;// s为走过的连续小道长度
            for(auto [v, t, c] : g[u]){
                if(t){
                    if((s + c) > 1000) continue;// 因为答案保证不超过1e6
                    ll nxt = len - 1ll * s * s + 1ll * (s + c) * (s + c);
                    int nv = (s + c) * n + v;
                    if(nxt < d[nv]) {
                        d[nv] = nxt;
                        pq.emplace(-d[nv], nv);
                    }
                }
                else{
                    if(len + c < d[v]){
                        d[v] = len + c;
                        pq.emplace(-d[v], v);
                    }
                }
            }
        }
        ll ans = inf;
        _rep(i, 0, 1001){
            ans = min(ans, d[i * n + n - 1]);
        }
        return ans;
    };
    cout << dij() << endl;
    return 0;
}