RT 44pts MLE

#include<bits/stdc++.h>
#define AC return 0;
#define _edge(u) for (int i = head[u], v = e[i].v, c = e[i].c, t = e[i].t; i; i = e[i].ne, v = e[i].v, c = e[i].c, t = e[i].t)
using namespace std;
const int maxn = 3e3 + 10;
int n, m, k;
char getc()
{
    static char ch[100000], *s, *t;
    return (s == t) && (t = (s = ch) + fread(ch, 1, 100000, stdin)), s == t ? EOF : *s++;
}
void read(int &x)
{
    char ch = getc();
    bool f = 0;
    x = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = 1;
        ch = getc();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getc();
    }
    f ? x = -x : 0;
}
void read(int &x,int &y){read(x),read(y);}

struct edge
{
    int v, ne, c, t;
    edge() {}
    edge(int v, int ne, int c, int t) : v(v), ne(ne), c(c), t(t) {}
}e[maxn<<1];
int head[maxn], _cnt;
void addedge(int u, int v, int c, int t)
{
    e[++_cnt] = edge(v, head[u], c, t);
    head[u] = _cnt;
}
struct edon
{
    int c, t, id;
    bool operator<(const edon &x) const
    {
        return (c * t) > (x.c * x.t);
    }
    edon() {}
    edon(int c, int t, int id) : c(c), t(t), id(id) {}
};

struct node
{
    int c, t;
    bool operator<(const node &x) const
    {
        return c * t < x.c * x.t;
    }
    bool operator>(const node &x) const
    {
        return c >= x.c && t >= x.t;
    }
    node() {}
    node(int c, int t,int id=0) : c(c), t(t){}
};
struct treap
{
    #define siz 1000
    node t[siz];
    int ls[siz], rs[siz], fa[siz];

    int rt, cnt, stac[siz], top;
    int new_node(int c, int _t)
    {
        if (top)
        {
            t[stac[top]] = node(c, _t);
            ls[stac[top]] = rs[stac[top]] = 0;
            return stac[top--];
        }
        t[++cnt] = node(c, _t);
        ls[cnt] = rs[cnt] = 0;
        return cnt;
    }
    int merge(int l, int r)
    {
        if (!l || !r)
            return l + r;
        if (t[l] < t[r])
        {
            rs[l] = merge(rs[l], r);
            return l;
        }
        else
        {
            ls[r] = merge(l, ls[r]);
            return r;
        }
    }
    void dfs(int &u, node x)
    {
        if (!u)
            return;
        if (t[u] > x)
        {
            stac[++top] = u;
            dfs(rs[u], x);
            u = merge(ls[u], rs[u]);
        }
        else if (t[ls[u]] > x)
            dfs(ls[u], x);
        else if (t[rs[u]] > x)
            dfs(rs[u], x);
    }
    void change(int &x, int y)
    {
        ls[y] = ls[x];
        rs[y] = rs[x];
        fa[y] = fa[x];
        stac[++top] = x;
        if (fa[x] != 0)
        {
            if (ls[fa[x]] == x)
                ls[fa[x]] = y;
            else
                rs[fa[x]] = y;
        }
        else
        {
            rt = y;
        }
        x = y;
    }
    bool insert(int &u, node x)
    {
        if (!u)
        {
            u = new_node(x.c, x.t);
            return 1;
        }
        if (t[u] > x)
        {
            change(u, new_node(x.c, x.t)), dfs(ls[u], x), dfs(rs[u], x);
            return 1;
        }
        if (x < t[u])
        {
            int tmp = new_node(x.c, x.t);
            if (t[u].c < x.c)
            {
                ls[tmp] = u;
            }
            else
            {
                rs[tmp] = u;
            }
            if (fa[u] != 0)
            {
                if (ls[fa[u]] == u)
                {
                    ls[fa[u]] = tmp;
                }
                else
                {
                    rs[fa[u]] = tmp;
                }
            }
            else
            {
                rt = tmp;
            }
            dfs(ls[u], x), dfs(rs[u], x);
            return 1;
        }
        if (x > t[u])
            return 0;
        if (x.c < t[u].c && insert(ls[u], x))
        {
            fa[ls[u]] = u;
            return 1;
        }
        else if (insert(rs[u], x))
        {
            fa[rs[u]] = u;
            return 1;
        }
        return 0;
    }
    bool insert(node x)
    {
        return insert(rt, x);
    }
} dis[maxn];

bool vis[maxn];
int cnt,num,ans[maxn];
void dfs(int u)
{
    cnt++;
    vis[u] = 1;
    _edge(u) if (!vis[v]) dfs(v);
}

void dij(int s)
{
    priority_queue<edon> q;
    q.push(edon(0, 0, s));
    while (!q.empty())
    {
        edon now = q.top();
        q.pop();
        if (!dis[now.id].insert(node(now.c, now.t)))
            continue;
        if (!vis[now.id])
        {
            vis[now.id] = 1;
            ans[now.id] = now.c * now.t;
            num++;
            if (num == cnt)
                return;
        }
        _edge(now.id)
            q.push(edon(now.c + c, now.t + t, v));
    }
    
}

void solve()
{
    memset(ans,-1,sizeof(ans));
    dij(1);
    for (int i = 2; i <= n; ++i)
        printf("%d\n", ans[i]);
}
void init()
{
    read(n,m);
    int u, v, c, t;
    for (int i = 1; i <= m; ++i)
        read(u, v), read(t, c), addedge(u, v, c, t), addedge(v, u, c, t);
    dfs(1);
    memset(vis,0,sizeof(vis));
}
int main()
{
    init();
    solve();
    AC
}