#include<bits/stdc++.h>
using namespace std;
#ifdef natural_selection
#include "../libra/misc/dbg.h"
#else
#define debug(...)
#define endl "\n"
#endif
template <typename Info, typename Tag>
class SegTreeChan
{
public:
int n;
vector<Info> infos;
vector<Tag> tags;
template<typename O>
void Recurse(int lb, int rb, bool update, O op)
{
auto rec = [&](int v, int l, int r, auto &&rec) -> void
{
Propagate(v, l, r);
if(l > r)
return;
if(lb <= l and r <= rb)
{
op(v, l, r);
return;
}
int m = (l + r)/2;
if(m >= lb)
rec(2 * v, l, m, rec);
else if(update)
Propagate(2 * v, l, m);
if(m + 1 <= rb)
rec(2 * v + 1, m + 1, r, rec);
else if(update)
Propagate(2 * v + 1, m + 1, r);
if(update)
infos[v] = infos[2 * v].Unite(infos[2 * v + 1]);
};
rec(1, 0, n - 1, rec);
};
SegTreeChan() : SegTreeChan(0) {};
SegTreeChan(int n) : SegTreeChan(vector<Info> (n)) {};
SegTreeChan(const vector<Info> &a) :
n((int)a.size()), infos(4 * n + 5), tags(4 * n + 5)
{
auto build = [&](int v, int l, int r, auto &&build) -> void
{
if(l > r)
return;
if(l == r)
{
infos[v] = Info(a[l]);
return;
}
int m = (l + r)/2;
build(v * 2, l, m, build);
build(v * 2 + 1, m + 1, r, build);
infos[v] = infos[v * 2].Unite(infos[v * 2 + 1]);
};
build(1, 0, n - 1, build);
};
void Propagate(int v, int l, int r)
{
if(tags[v].Empty())
return;
tags[v].ApplyTo(infos[v], l, r);
if(l != r)
{
tags[v].ApplyTo(tags[2 * v]);
tags[v].ApplyTo(tags[2 * v + 1]);
}
tags[v] = Tag();
}
void Modify(int lb, int rb, const Tag &tag)
{
Recurse(lb, rb, true, [&](int v, int l, int r)
{
tag.ApplyTo(tags[v]);
Propagate(v, l, r);
});
}
void Set(int p, const Info &info)
{
Recurse(p, p, true, [&](int v, int l, int r)
{
infos[v] = info;
});
}
void Add(int p, const Info &info)
{
Recurse(p, p, true, [&](int v, int l, int r)
{
infos[v] = infos[v].Unite(info);
Propagate(v, l, r);
});
}
Info Query(int lb, int rb)
{
Info res = Info();
Recurse(lb, rb, false, [&](int v, int l, int r)
{
res = res.Unite(infos[v]);
});
return res;
}
Info Get(int p)
{
Info res = Info();
Recurse(p, p, false, [&](int v, int l, int r)
{
res = infos[v];
});
return res;
}
};
const int64_t inf = numeric_limits<int64_t>::max();
class InfoChan
{
public:
pair<int64_t, int> mn;
InfoChan() : mn(make_pair(inf, -1)) {}; //if second element is -1, it means no element
InfoChan(int i, int64_t x) : mn(x, i) {};
InfoChan Unite(InfoChan b) const
{
InfoChan res;
if(mn.second == -1)
res.mn = b.mn;
else if(b.mn.second == -1)
res.mn = mn;
else
res.mn = min(mn, b.mn);
return res;
}
static InfoChan GetDefault([[maybe_unused]] int l, [[maybe_unused]] int r)
{
return InfoChan();
}
};
class TagChan
{
public:
int64_t paint;
TagChan() : paint(inf) {};
TagChan(int x) : paint(x) {};
bool ApplyTo(InfoChan &a, [[maybe_unused]] int l, [[maybe_unused]] int r) const
{
if(a.mn.second != -1)
a.mn.first = min(a.mn.first, paint);
return true;
}
void ApplyTo(TagChan &t) const
{
t.paint = min(t.paint, paint);
}
bool Empty() const
{
return paint == inf;
}
};
int32_t main()
{
ios_base::sync_with_stdio(false), cin.tie(NULL);
int n, m;
cin >> n >> m;
vector<vector<array<int, 3>>> adj(n);
for(int i = 0; i < m; i ++)
{
int u, l, r, c;
cin >> u >> l >> r >> c;
-- u, -- l, -- r, c;
adj[u].push_back({l, r, c});
}
vector<InfoChan> a(n);
for(int i = 0; i < n; i ++)
a[i].mn = {(i == 0 ? 0 : inf), i};
SegTreeChan<InfoChan, TagChan> rq(a);
vector<int64_t> dis(n);
for(int i = 0; i < n; i ++)
{
auto [d, u] = rq.Query(0, n - 1).mn;
dis[u] = d;
assert(u != -1);
for(auto [l, r, c] : adj[u])
rq.Modify(l, r, TagChan(d + c));
rq.Set(u, InfoChan());
}
for(int u = 0; u < n; u ++)
cout << dis[u] << " ";
cout << endl;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNpZmRlZiBuYXR1cmFsX3NlbGVjdGlvbgojaW5jbHVkZSAiLi4vbGlicmEvbWlzYy9kYmcuaCIKI2Vsc2UKI2RlZmluZSBkZWJ1ZyguLi4pCiNkZWZpbmUgZW5kbCAiXG4iCiNlbmRpZgoKdGVtcGxhdGUgPHR5cGVuYW1lIEluZm8sIHR5cGVuYW1lIFRhZz4KY2xhc3MgU2VnVHJlZUNoYW4KewpwdWJsaWM6CiAgICBpbnQgbjsKICAgIHZlY3RvcjxJbmZvPiBpbmZvczsKICAgIHZlY3RvcjxUYWc+IHRhZ3M7CgogICAgdGVtcGxhdGU8dHlwZW5hbWUgTz4KICAgIHZvaWQgUmVjdXJzZShpbnQgbGIsIGludCByYiwgYm9vbCB1cGRhdGUsIE8gb3ApCiAgICB7CiAgICAgICAgYXV0byByZWMgPSBbJl0oaW50IHYsIGludCBsLCBpbnQgciwgYXV0byAmJnJlYykgLT4gdm9pZAogICAgICAgIHsKICAgICAgICAgICAgUHJvcGFnYXRlKHYsIGwsIHIpOwoKICAgICAgICAgICAgaWYobCA+IHIpCiAgICAgICAgICAgICAgICByZXR1cm47CiAgICAgICAgICAgIAogICAgICAgICAgICBpZihsYiA8PSBsIGFuZCByIDw9IHJiKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBvcCh2LCBsLCByKTsKICAgICAgICAgICAgICAgIHJldHVybjsKICAgICAgICAgICAgfQogICAgICAgICAgICAKICAgICAgICAgICAgaW50IG0gPSAobCArIHIpLzI7CiAgICAgICAgICAgIAogICAgICAgICAgICBpZihtID49IGxiKQogICAgICAgICAgICAgICAgcmVjKDIgKiB2LCBsLCBtLCByZWMpOwogICAgICAgICAgICBlbHNlIGlmKHVwZGF0ZSkKICAgICAgICAgICAgICAgIFByb3BhZ2F0ZSgyICogdiwgbCwgbSk7CgogICAgICAgICAgICBpZihtICsgMSA8PSByYikKICAgICAgICAgICAgICAgIHJlYygyICogdiArIDEsIG0gKyAxLCByLCByZWMpOwogICAgICAgICAgICBlbHNlIGlmKHVwZGF0ZSkKICAgICAgICAgICAgICAgIFByb3BhZ2F0ZSgyICogdiArIDEsIG0gKyAxLCByKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGlmKHVwZGF0ZSkKICAgICAgICAgICAgICAgIGluZm9zW3ZdID0gaW5mb3NbMiAqIHZdLlVuaXRlKGluZm9zWzIgKiB2ICsgMV0pOwogICAgICAgIH07CiAgICAgICAgcmVjKDEsIDAsIG4gLSAxLCByZWMpOwogICAgfTsKCiAgICBTZWdUcmVlQ2hhbigpIDogU2VnVHJlZUNoYW4oMCkge307CiAgICBTZWdUcmVlQ2hhbihpbnQgbikgOiBTZWdUcmVlQ2hhbih2ZWN0b3I8SW5mbz4gKG4pKSB7fTsKICAgIFNlZ1RyZWVDaGFuKGNvbnN0IHZlY3RvcjxJbmZvPiAmYSkgOiAKICAgIG4oKGludClhLnNpemUoKSksIGluZm9zKDQgKiBuICsgNSksIHRhZ3MoNCAqIG4gKyA1KQogICAgewogICAgICAgIGF1dG8gYnVpbGQgPSBbJl0oaW50IHYsIGludCBsLCBpbnQgciwgYXV0byAmJmJ1aWxkKSAtPiB2b2lkCiAgICAgICAgewogICAgICAgICAgICBpZihsID4gcikKICAgICAgICAgICAgICAgIHJldHVybjsKICAgICAgICAgICAgaWYobCA9PSByKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpbmZvc1t2XSA9IEluZm8oYVtsXSk7CiAgICAgICAgICAgICAgICByZXR1cm47CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaW50IG0gPSAobCArIHIpLzI7CiAgICAgICAgICAgIGJ1aWxkKHYgKiAyLCBsLCBtLCBidWlsZCk7CiAgICAgICAgICAgIGJ1aWxkKHYgKiAyICsgMSwgbSArIDEsIHIsIGJ1aWxkKTsKICAgICAgICAgICAgaW5mb3Nbdl0gPSBpbmZvc1t2ICogMl0uVW5pdGUoaW5mb3NbdiAqIDIgKyAxXSk7CiAgICAgICAgfTsKICAgICAgICBidWlsZCgxLCAwLCBuIC0gMSwgYnVpbGQpOwogICAgfTsKCiAgICB2b2lkIFByb3BhZ2F0ZShpbnQgdiwgaW50IGwsIGludCByKQogICAgewogICAgICAgIGlmKHRhZ3Nbdl0uRW1wdHkoKSkKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIHRhZ3Nbdl0uQXBwbHlUbyhpbmZvc1t2XSwgbCwgcik7CiAgICAgICAgaWYobCAhPSByKQogICAgICAgIHsKICAgICAgICAgICAgdGFnc1t2XS5BcHBseVRvKHRhZ3NbMiAqIHZdKTsKICAgICAgICAgICAgdGFnc1t2XS5BcHBseVRvKHRhZ3NbMiAqIHYgICsgMV0pOwogICAgICAgIH0KICAgICAgICB0YWdzW3ZdID0gVGFnKCk7CiAgICB9CgogICAgdm9pZCBNb2RpZnkoaW50IGxiLCBpbnQgcmIsIGNvbnN0IFRhZyAmdGFnKQogICAgewogICAgICAgIFJlY3Vyc2UobGIsIHJiLCB0cnVlLCBbJl0oaW50IHYsIGludCBsLCBpbnQgcikKICAgICAgICB7CiAgICAgICAgICAgIHRhZy5BcHBseVRvKHRhZ3Nbdl0pOwogICAgICAgICAgICBQcm9wYWdhdGUodiwgbCwgcik7CiAgICAgICAgfSk7CiAgICB9CiAgICB2b2lkIFNldChpbnQgcCwgY29uc3QgSW5mbyAmaW5mbykKICAgIHsKICAgICAgICBSZWN1cnNlKHAsIHAsIHRydWUsIFsmXShpbnQgdiwgaW50IGwsIGludCByKQogICAgICAgIHsKICAgICAgICAgICAgaW5mb3Nbdl0gPSBpbmZvOwogICAgICAgIH0pOwogICAgfQogICAgdm9pZCBBZGQoaW50IHAsIGNvbnN0IEluZm8gJmluZm8pCiAgICB7CiAgICAgICAgUmVjdXJzZShwLCBwLCB0cnVlLCBbJl0oaW50IHYsIGludCBsLCBpbnQgcikKICAgICAgICB7CiAgICAgICAgICAgIGluZm9zW3ZdID0gaW5mb3Nbdl0uVW5pdGUoaW5mbyk7CiAgICAgICAgICAgIFByb3BhZ2F0ZSh2LCBsLCByKTsKICAgICAgICB9KTsKICAgIH0KICAgIEluZm8gUXVlcnkoaW50IGxiLCBpbnQgcmIpCiAgICB7CiAgICAgICAgSW5mbyByZXMgPSBJbmZvKCk7CiAgICAgICAgUmVjdXJzZShsYiwgcmIsIGZhbHNlLCBbJl0oaW50IHYsIGludCBsLCBpbnQgcikKICAgICAgICB7CiAgICAgICAgICAgIHJlcyA9IHJlcy5Vbml0ZShpbmZvc1t2XSk7CiAgICAgICAgfSk7CiAgICAgICAgcmV0dXJuIHJlczsKICAgIH0KICAgIEluZm8gR2V0KGludCBwKQogICAgewogICAgICAgIEluZm8gcmVzID0gSW5mbygpOwogICAgICAgIFJlY3Vyc2UocCwgcCwgZmFsc2UsIFsmXShpbnQgdiwgaW50IGwsIGludCByKQogICAgICAgIHsKICAgICAgICAgICAgcmVzID0gaW5mb3Nbdl07CiAgICAgICAgfSk7CiAgICAgICAgcmV0dXJuIHJlczsKICAgIH0KfTsKCmNvbnN0IGludDY0X3QgaW5mID0gbnVtZXJpY19saW1pdHM8aW50NjRfdD46Om1heCgpOwoKY2xhc3MgSW5mb0NoYW4KewpwdWJsaWM6CiAgICBwYWlyPGludDY0X3QsIGludD4gbW47CgogICAgSW5mb0NoYW4oKSA6IG1uKG1ha2VfcGFpcihpbmYsIC0xKSkge307ICAgICAvL2lmIHNlY29uZCBlbGVtZW50IGlzIC0xLCBpdCBtZWFucyBubyBlbGVtZW50CiAgICBJbmZvQ2hhbihpbnQgaSwgaW50NjRfdCB4KSA6IG1uKHgsIGkpIHt9OwoKICAgIEluZm9DaGFuIFVuaXRlKEluZm9DaGFuIGIpIGNvbnN0IAogICAgewogICAgICAgIEluZm9DaGFuIHJlczsKICAgICAgICBpZihtbi5zZWNvbmQgPT0gLTEpCiAgICAgICAgICAgIHJlcy5tbiA9IGIubW47CiAgICAgICAgZWxzZSBpZihiLm1uLnNlY29uZCA9PSAtMSkKICAgICAgICAgICAgcmVzLm1uID0gbW47CiAgICAgICAgZWxzZQogICAgICAgICAgICByZXMubW4gPSBtaW4obW4sIGIubW4pOwogICAgICAgIHJldHVybiByZXM7CiAgICB9CiAgICBzdGF0aWMgSW5mb0NoYW4gR2V0RGVmYXVsdChbW21heWJlX3VudXNlZF1dIGludCBsLCBbW21heWJlX3VudXNlZF1dIGludCByKQogICAgewogICAgICAgIHJldHVybiBJbmZvQ2hhbigpOwogICAgfQp9OwpjbGFzcyBUYWdDaGFuCnsKcHVibGljOgogICAgaW50NjRfdCBwYWludDsKCiAgICBUYWdDaGFuKCkgOiBwYWludChpbmYpIHt9OwogICAgVGFnQ2hhbihpbnQgeCkgOiBwYWludCh4KSB7fTsKCiAgICBib29sIEFwcGx5VG8oSW5mb0NoYW4gJmEsIFtbbWF5YmVfdW51c2VkXV0gaW50IGwsIFtbbWF5YmVfdW51c2VkXV0gaW50IHIpIGNvbnN0CiAgICB7CiAgICAgICAgaWYoYS5tbi5zZWNvbmQgIT0gLTEpCiAgICAgICAgICAgIGEubW4uZmlyc3QgPSBtaW4oYS5tbi5maXJzdCwgcGFpbnQpOwogICAgICAgIHJldHVybiB0cnVlOwogICAgfQogICAgdm9pZCBBcHBseVRvKFRhZ0NoYW4gJnQpIGNvbnN0CiAgICB7CiAgICAgICAgdC5wYWludCA9IG1pbih0LnBhaW50LCBwYWludCk7CiAgICB9CiAgICBib29sIEVtcHR5KCkgY29uc3QKICAgIHsKICAgICAgICByZXR1cm4gcGFpbnQgPT0gaW5mOwogICAgfQp9OwoKCmludDMyX3QgbWFpbigpCnsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpLCBjaW4udGllKE5VTEwpOwoKICAgIGludCBuLCBtOwogICAgY2luID4+IG4gPj4gbTsKCiAgICB2ZWN0b3I8dmVjdG9yPGFycmF5PGludCwgMz4+PiBhZGoobik7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbTsgaSArKykKICAgIHsKICAgICAgICBpbnQgdSwgbCwgciwgYzsKICAgICAgICBjaW4gPj4gdSA+PiBsID4+IHIgPj4gYzsKICAgICAgICAtLSB1LCAtLSBsLCAtLSByLCBjOwogICAgICAgIGFkalt1XS5wdXNoX2JhY2soe2wsIHIsIGN9KTsKICAgIH0KCiAgICB2ZWN0b3I8SW5mb0NoYW4+IGEobik7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSArKykKICAgICAgICBhW2ldLm1uID0geyhpID09IDAgPyAwIDogaW5mKSwgaX07CgogICAgU2VnVHJlZUNoYW48SW5mb0NoYW4sIFRhZ0NoYW4+IHJxKGEpOwoKICAgIHZlY3RvcjxpbnQ2NF90PiBkaXMobik7CgogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkgKyspCiAgICB7CiAgICAgICAgYXV0byBbZCwgdV0gPSBycS5RdWVyeSgwLCBuIC0gMSkubW47CiAgICAgICAgZGlzW3VdID0gZDsKCiAgICAgICAgYXNzZXJ0KHUgIT0gLTEpOwoKICAgICAgICBmb3IoYXV0byBbbCwgciwgY10gOiBhZGpbdV0pCiAgICAgICAgICAgIHJxLk1vZGlmeShsLCByLCBUYWdDaGFuKGQgKyBjKSk7CgogICAgICAgIHJxLlNldCh1LCBJbmZvQ2hhbigpKTsKICAgIH0KCiAgICBmb3IoaW50IHUgPSAwOyB1IDwgbjsgdSArKykKICAgICAgICBjb3V0IDw8IGRpc1t1XSA8PCAiICI7CiAgICBjb3V0IDw8IGVuZGw7Cn0=