#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const int maxn=5e2+;

const int maxm=1e5+;

int n,m;

struct edge{

    int t;

    int to;

    int nxt;

    ll w;

}e[*maxm];

struct node{

    int id;

    ll d;

    ll fa;

    node(int _id,ll _d,ll _fa):id(_id),d(_d),fa(_fa){}

    bool operator < (const node& a) const{

        if(d!=a.d) return d>a.d;

        return fa>a.fa;

    }

};

int head[maxn];

int tot;

ll dis[maxn];

ll fa[maxn];

bool vis[maxn];

void init(){

    memset(head,-,sizeof(head));

    tot=;

}

void add(int t,int u,int v,ll w){

    e[tot].t=t;

    e[tot].to=v;

    e[tot].w=w;

    e[tot].nxt=head[u];

    head[u]=tot++;

}

ll dijkstra(int s){

    memset(dis,inf,sizeof(dis));

    memset(fa,inf,sizeof(fa));

    memset(vis,false,sizeof(vis));

    dis[s]=,fa[s]=;

    priority_queue<node> Q;

    Q.push(node(s,dis[s],fa[s]));

    while(!Q.empty()){

        node q=Q.top();

        Q.pop();

        int u=q.id;

        if(vis[u]) continue;

        vis[u]=true;

        for(int i=head[u];i!=-;i=e[i].nxt){

            int t=e[i].t;

            int v=e[i].to;

            ll w=e[i].w;

            if(t==){

                if(dis[u]+w<=dis[v]){

                    dis[v]=dis[u]+w;

                    fa[v]=;

                    Q.push(node(v,dis[v],fa[v]));

                }

            }else{

                ll tmp=(fa[u]+w)*(fa[u]+w)+dis[u]-fa[u]*fa[u];

                if(tmp<dis[v]){

                    dis[v]=tmp;

                    fa[v]=fa[u]+w;

                    Q.push(node(v,dis[v],fa[v]));

                }else if(tmp==dis[v]){

                    if(fa[u]+w<fa[v]){

                        fa[v]=fa[u]+w;

                        Q.push(node(v,dis[v],fa[v]));

                    }

                }

            }

        }

    }

    return dis[n];

}

int main(){

    while(~scanf("%d%d",&n,&m)){

        init();

        int t,u,v;

        ll w;

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

            scanf("%d%d%d%lld",&t,&u,&v,&w);

            add(t,u,v,w);

            add(t,v,u,w);

        }

        ll ans=dijkstra();

        printf("%lld\n",ans);

    }

    return ;

}