#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct Plane{
    int leave,des,arrive;
    bool operator<(Plane& w)const
    {
        return leave<w.leave;
    }
};
vector<Plane> v[N];
int e[N],dist[N],pos[N];
void dfs(int u,int total) //离开u城的最早的时间为t
{
    for(int i=pos[u];i>=0;i--)
    {
        Plane t=v[u][i];
        if(t.leave<total) //如果当前的飞机不可以，那么前面的也一定不可以
        {
            break;
        }
        dist[t.des]=min(dist[t.des],t.arrive); //更新后面的最早结束时间
        pos[u]=i-1; //下次就不走这条线了
        dfs(t.des,t.arrive+e[t.des]);//搜索下条可以走的路线
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int from;
        Plane t;
        cin>>from>>t.leave>>t.des>>t.arrive;
        v[from].push_back(t); //加入到同个航线
    }
    for(int i=1;i<=n;i++)
    {
        cin>>e[i];
        pos[i]=v[i].size()-1;
        sort(v[i].begin(),v[i].end()); //按照离开时间从小到大排序
    }
    memset(dist,0x3f,sizeof dist);
    dist[1]=0; //起点距离
    dfs(1,0); //开始搜索
    for(int i=1;i<=n;i++)
    {
        if(dist[i]==0x3f3f3f3f) cout<<-1<<endl;
        else cout<<dist[i]<<endl;
    }
    return 0;
}