#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N=3000,SQ=1000;
int t[N],c[N],vis[N];
vector<pair<int,int>> ma[N];
typedef long long ll;
#define state pair<pair<ll,int>,pair<ll,ll>>
#define d first.first
#define v first.second
#define st second.first
#define sc second.second
ll dp[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
{
int x,y;
cin>>x>>y>>t[i]>>c[i];
ma[x].push_back({i,y});
ma[y].push_back({i,x});
}
for(int i=0;i<=n;i++)
{
dp[i]=1e15;
}
priority_queue<state,vector<state>,greater<state>>pq;
dp[1]=0;
pq.push(make_pair(make_pair(0,1),make_pair(0,0)));
while(pq.size()>0)
{
auto p=pq.top();
pq.pop();
if(vis[p.v]>=SQ)
{
continue;
}
vis[p.v]++;
for(auto [id,u]:ma[p.v])
{
ll cd=(p.st+t[id])*(p.sc+c[id]);
dp[u]=min(dp[u],cd);
pq.push(make_pair(make_pair(cd,u),make_pair(p.st+t[id],p.sc+c[id])));
}
}
for(int i=2;i<=n;i++)
{
if(dp[i]==1e15)
{
cout<<-1<<endl;
}
else
{
cout<<dp[i]<<endl;
}
}
}
