#include <bits/stdc++.h>
using namespace std;

#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define REVERSE(v) reverse((v).begin(), (v).end())
#define MAX(v) (*max_element((v).begin(), (v).end()))
#define MIN(v) (*min_element((v).begin(), (v).end()))
#define pb push_back
#define FOR(i, n) for(int i = 0; i < (n); i++)
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

const int mod = 1e9 + 7;
const int mod2 = 998244353;

inline void modsum(int&a, int b){a += b;if(a >= mod) a -= mod;if(a < 0) a += mod;}
inline void modmul(int&a, int b){a = 1ll*a*b % mod;}
inline int modexp(ll b, ll p){b %= mod;int res = 1;int mul = b;while(p){if(p&1) modmul(res, mul);p >>= 1;modmul(mul, mul);}return res;}

const int N = 1e5 + 5;
struct E{
	int u, c, d;
};
int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);
	int n, m; cin>>n>>m;
	vector<E> g[n+1];
	FOR(i, m){
		int a, b, c, d; cin>>a>>b>>c>>d;
		g[a].pb(E{b, c, d});
		g[b].pb(E{a, c, d});
	}
	set<pair<long long, int>> q;
	q.insert({0, 1});
	long long dist[n+1];
	FOR(i, n+1) dist[i] = 1e18;
	bool vis[n+1] = {};
	dist[1] = 0;
	while(!q.empty()){
		pair<long long, int> foo = *q.begin();
		q.erase(q.begin());
		int cur = foo.second;
		if(vis[cur]) continue;
		vis[cur] = true;
		ll cur_t = dist[cur];
		for(E& nxt: g[cur]){
			int u = nxt.u, c = nxt.c, d = nxt.d;
			//init. cost = c + (d/(cur_t+1))
			//min(x + d/(cur_t+1+x)) ?
			ll x = max(0ll, (ll)sqrt(d) - cur_t);
			ll mn = c + d/(cur_t+1);
			for(ll i = max(0ll, x-500); i <= x+500; i++){
				mn = min(mn, c + i + d/(cur_t+1+i));
			}
			if(dist[u] <= dist[cur] + mn) continue;
			dist[u] = dist[cur] + mn;
			q.insert({dist[u], u});
		}
	}
	if(!vis[n]) cout<<-1;
	else cout<<dist[n];
}
//#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define SZ(x) ((int)x.size())
#define uni(x) sort(all(x)),x.resize(unique(all(x))-x.begin());
#define GETPOS(c,x) (lower_bound(all(c),x)-c.begin())
#define lown1(x,val) low(in(x),val)-x
#define lowm1(x,val) low(im(x),val)-x
#define low1(x,nums,val) low(x+1,x+nums+1,val)-x
#define mst(x,val) memset((x),val,sizeof((x)))
#define ls rt<<1
#define rs rt<<1|1
#define lson rt<<1,l,M
#define rson rt<<1|1,M+1,r
#define PI acos(-1)
#define MM int M=(l+r)>>1;
#define fu(i,r,t) for(int i=r;i<=t;i++)
#define fd(i,r,t) for(int i=r;i>=t;i--)
#define fh(i,be,e) for(int i=head[be];~i;i=e[i].next)
#define fa(i,V) for(auto i:V)
#define far(i,V) for(auto &i:V)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lcm(a,b) ((a)*(b))/__gcd(a,b)
#define cp(i,ans) printf("%.if",ans);
#define cpp(i,ans) cout<<setprecision(i)<<fixed<<ans<<endl;
#define ppb pop_back
#define ppf pop_front
#define pb push_back
#define pf push_front
#define pq priority_queue
#define lowbit(x) ((x)&(-x))
#define all(V) V.begin(),V.end()
#define ms multiset
#define mod(x) (((x)<0)?(x)%mo_num+mo_num:(x)%mo_num)
#define vc vector
#define vct vector<int>
#define SET set<int>
#define dq deque<int>
#define out(i) cout<<(i)<<endl;
#define fi first
#define se second
#define fun(i) fu(i,1,n)
#define fut(i) fu(i,1,t)
#define fum(i) fu(i,1,m)
#define ld long double
#define umap unordered_map
#define Umap unordered_map<int,int>
#define P pair<int,int>
#define mk make_tuple
#define eps 1e-6
//Remember cancel"#define endl '\n'" in interactive questions or use "<<flush"
#define endl '\n'
#define low lower_bound
#define upp upper_bound
#define yn(key) out(key?"YES":"NO")
//#define yn(key) out(key?"Yes":"No")
#define in(i) i+1,i+1+n
#define im(i) i+1,i+1+m
#define ik(i,k) i+1,i+1+k
#define bffs(i) __builtin_ffs(i)
#define bcount(i) __builtin_popcount(i)
#define bone(i) ((1<<i)-1)
#define db double
#define ll long long
#define got(container,num) get<num-1>(container)
#define int long long
#define print(a,n) fun(i)cout<<a[i]<<(i!=n?' ':endl);
#define outcase(x) cout<<"Case #"<<(++case_of_T)<<": "<<(x)<<endl;
#define ptcase(x) printf("Case #%d: %d\n",++case_of_T,x);
#define plcase(x) printf("Case #%lld: %lld\n",++case_of_T,x);
using namespace std;
//Remember to cancel the line below and declare INT=INT_MAX/2; when you want to change long to int
const int INF=LLONG_MAX/4,SINF=0x3f3f3f3f,Lim=1<<20,MINF=LLONG_MAX;
//const int INF=INT_MAX/4,SINF=0x3f;
// use C:printf("%.16f", x);  ->  printf("%.10f", x); can accelerate the program
const int dx[]={0,0,-1,1},dy[]={-1,1,0,0};//down up left right
const int maxn=1e6+1e5;
int mo_num=1e9+7;
//const int mo_num=998244353;
int n,m,t,a[maxn],b[maxn],ans,case_of_T;
int c[maxn],d[maxn];
vc<P>have;
void change(int z,int y)
{
    have.pb({z,y});
    swap(c[z],c[y]);
    d[c[z]]=z,d[c[y]]=y;
}
void deal(int x)
{
    if(b[c[x]]<a[d[x]]){
        change(x,d[x]);
        return ;
    }
    while(b[c[x]]>=a[d[x]] && d[x]!=x)deal(d[x]);
    if(d[x]!=x)change(x,d[x]);
}
void solve()
{
    cin>>n;
    fun(i)cin>>a[i];
    fun(i)cin>>b[i];
    fun(i) {
        cin >> c[i], d[c[i]] = i;
        if(c[i]!=i && b[c[i]]>=a[i]){out(-1)return;}
    }
    fun(i)
    {
        if(d[i]!=i)deal(i);
    }
    out(have.size())
    fa(i,have)cout<<i.fi<<" "<<i.se<<endl;
    return ;
}
main()
{
    IOS
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

