#include <bits/stdc++.h>

using namespace std;
using ll =long long;
typedef pair<ll,ll> P;
#define SORT(a) sort((a).begin(),(a).end())
#define REV(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}
void mswap(ll &a, ll &b){ if(a >= b) swap(a,b); }
void rswap(ll &a, ll &b){ if(a <= b) swap(a,b); }

const int dy[] = {0,0,1,-1};
const int dx[] = {1,-1,0,0};
const ll mod = 1e9+7;
const ll MOD = 998244353;
const double PI=3.14159265358979323846;
const int inf = 1001001001;
const ll INF = 1'000'000'000'000'000'000;
const ll minf = -inf;

ll dp[200005][2];
//Write From this Line
int main()
{
	int n;
	cin >> n;
	vector<ll> x(n), c(n);
	rep(i,n) cin >> x[i] >> c[i];
	vector<ll> l(n+1,1'000'000'001);
    vector<ll> r(n+1,-1'000'000'001);
	rep(i,n){
		int color = c[i];

		chmin(l[color], x[i]);
		chmax(r[color], x[i]);
	}
	rep(i,200005) rep(j,2) dp[i][j] = INF;
	dp[0][0] = 0;
	dp[0][1] = 0;
	// 0:l側にいる 1:R側にいる
	ll tmpL = 0; // 座標
	ll tmpR = 0;
	rep(i,n+1){
		if(i == 0) continue;
		if(l[i] == 1'000'000'001 || r[i] == - 1'000'000'001){
			dp[i][0] = dp[i-1][0];
			dp[i][1] = dp[i-1][1];
		   	continue;
		}
		rep(j,2){
			if(j == 0){
				//取り終わったらL側l[i]に行く というか、R側から取り始めて、最後がL側
				// tmpL -> r[i] -> l[i]
				chmin(dp[i][j], dp[i-1][0] + abs(r[i] - tmpL) + abs(r[i] - l[i])); 
				// tmpR -> r[i] -> l[i]
				chmin(dp[i][j], dp[i-1][1] + abs(r[i] - tmpR) + abs(r[i] - l[i])); 
			} else {
				// 取り終わったらR側r[i]に行く L側Start最後がR
				// tmpL -> l[i] -> r[i]
				chmin(dp[i][j], dp[i-1][0] + abs(l[i] - tmpL) + abs(r[i] - l[i])); 
				// tmpR -> l[i] -> r[i]
				chmin(dp[i][j], dp[i-1][1] + abs(l[i] - tmpR) + abs(r[i] - l[i])); 
			}
		}
		tmpL = l[i];
		tmpR = r[i];
	}
	ll ans = min(dp[n][0] + abs(tmpL), dp[n][1] + abs(tmpR));
	cout << ans << endl;
}

/*
    author : Aryan Agarwal, IIT KGP
    created : 06-February-2021 18:04:32 IST
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int mxn = 2000;
const long long INF = 2e18;
const int32_t M = 1000000007; /*more than 1e9 */ /*7 + 1e9*/
// const int32_t M = 998244353; /*less than 1e9 */   /*1 + 7*17*(1<<23) */
const long double pie = acos(-1);

#define X first
#define Y second
#define pb push_back
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define F(i, a, b) for (int i = a; i <= b; i++)
#define RF(i, a, b) for (int i = a; i >= b; i--)

#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}

int n,m;
vector< vector<pair <int,int> > >  adj(mxn+1);
vector <int> ans(mxn+1,INF);
vector <bool> vis(mxn+1,false);

void dijkstra(int s, vector<int> & d) {
    int n = adj.size();
    d.assign(n, INF);
    // p.assign(n, -1);

    d[s] = 0;
    using pii = pair<int, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    while (!q.empty()) {
        int v = q.top().second;
        int d_v = q.top().first;
        q.pop();
        if (d_v != d[v])
            continue;

        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                // p[to] = v;
                q.push({d[to], to});
            }
        }
    }
}

void solve_LOG()
{
    cin>>n>>m;
    F(i,1,m)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(a==b)ans[a]=min(ans[a],c);
        else adj[a].pb({b,c});
        
    }

    vector< vector<int> > dis(n+1);

    F(i,1,n)
    {
        dijkstra(i,dis[i]);
    }

    F(i,1,n)
    {
        F(j,i+1,n)
        {
            if(dis[i][j]!=INF && dis[j][i]!=INF)
            {
                ans[i]=min(ans[i],dis[i][j]+dis[j][i]);
                ans[j]=min(ans[j],dis[j][i]+dis[i][j]);
            }
        }
    }

    F(i,1,n)
    {
        if(ans[i]==INF)ans[i]=-1;
        cout<<ans[i];
        cout<<"\n";
    }

}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
#ifdef ARYAN_SIEVE
    // defualt mxn_sieve = 1e5
    sieve();
#endif
#ifdef ARYAN_SEG_SIEVE
    // default [L,R] = [1,1e5]
    segmented_sieve();
#endif
#ifdef ARYAN_FACT
    // default mxn_fact = 1e5
    fact_init();
#endif
    // cout<<fixed<<setprecision(10);
    int _t=1;
    // cin>>_t;
    for (int i=1;i<=_t;i++)
    {
        // cout<<"Case #"<<i<<": ";
        solve_LOG();
    }
    return 0;
}