var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var arr=input.trim().split("\n");
var nk=arr.shift().split(" ").map(Number);
var n=nk[0];
var k=nk[1];
var cr=[""];
for(var i=0;i<n;i++)cr.push(arr.shift().split(" ").map(Number));
var ab=[];
for(var i=0;i<k;i++)ab.push(arr.shift().split(" ").map(Number));
var start=1;
var end=n;

var dp=[];
for(var i=0;i<=n;i++){
dp[i]=[];
for(var j=0;j<=n;j++){
dp[i][j]=Infinity;
}
}

dp[1][0]=0;
var ary=[1];
var obj={};
while(true){
if(ary.length==0)break;
var s=ary.shift();
if(obj.hasOwnProperty(s))continue;
obj[s]=true;
ab.forEach(function(v){
var a=v[0];
var b=v[1];
if(a==s){
var cost=cr[a][0];
var r=cr[a][1]-1;
for(var i=0;i<=r;i++)dp[b][i]=Math.min(dp[b][i],dp[a][0]+cost);
dp[a].forEach(function(sum,index){
if(index!=0)dp[b][index-1]=Math.min(dp[b][index-1],sum);
});
ary.push(b);
}else if(b==s){
var cost=cr[b][0];
var r=cr[b][1]-1;
for(var i=0;i<=r;i++)dp[a][i]=Math.min(dp[a][i],dp[b][0]+cost);
dp[b].forEach(function(sum,index){
if(index!=0)dp[a][index-1]=Math.min(dp[a][index-1],sum);
});
ary.push(a);
}
});

}

var ary=[1];
var obj={};
while(true){
if(ary.length==0)break;
var s=ary.shift();
if(obj.hasOwnProperty(s))continue;
obj[s]=true;
ab.forEach(function(v){
var a=v[0];
var b=v[1];
if(a==s){
var cost=cr[a][0];
var r=cr[a][1]-1;
for(var i=0;i<=r;i++)dp[b][i]=Math.min(dp[b][i],dp[a][0]+cost);
dp[a].forEach(function(sum,index){
if(index!=0)dp[b][index-1]=Math.min(dp[b][index-1],sum);
});
ary.push(b);
}else if(b==s){
var cost=cr[b][0];
var r=cr[b][1]-1;
for(var i=0;i<=r;i++)dp[a][i]=Math.min(dp[a][i],dp[b][0]+cost);
dp[b].forEach(function(sum,index){
if(index!=0)dp[a][index-1]=Math.min(dp[a][index-1],sum);
});
ary.push(a);
}
});

}


var ans=Infinity;
dp[end].forEach(function(v){
   ans=Math.min(ans,v);
});
console.log(ans);