[TIOJ 1071] 字串消去問題(Censorship)

作法：

如果我們能計算出一個二維陣列$ok$，其中$ok[i][j]$代表$S[i,...,j]$是否可以恰好被完整刪除，那麼就可以用簡單的DP求出最後答案了。首先我們知道$S$中有許多子字串是可以「直接被刪除的」，也就是他剛好等於給定字串集合裡的其中一個字串。當我們把這種子字串刪掉時，有可能會造成新的子字串可以被刪掉。例如原字串為$caabbd$，並且可以刪掉$ab$，那麼在第二層就可以把$aabb$刪掉了，也就是$ok[2][5]=1$。我們可以概念上的稱「可直接被刪除的子字串」為一級的子字串，需要經過兩層才能刪除的為二級的子字串，那麼可知一個有辦法被刪除的子字串至多$n$層。因此我們要想辦法從$i$級的子字串的$ok$陣列推出$i+1$級的陣列，重複$n$次就可以得到我們要的$ok$陣列了。假設我們現在想知道$S[L,...,R]$這個子字串是否能在第$k+1$層時被刪掉，那麼考慮所有$S[L,...,R]$的可在第$k$層時被刪掉的子字串們，那麼$S[L,...,R]$可以在第$k+1$層時被刪掉若且唯若：存在$(l_1,r_1),...,(l_t,r_t)$滿足$L\leq l_1\leq r_1 < l_2 \leq r_2 < ... < l_t \leq r_t \leq R$，並且$S[l_i,...,r_i]$均可以在第$k$層被刪掉，還有把$S[L,...,R]$扣掉所有$S[l_i,...,r_i]$後所得到的字串是可以直接刪除的。有了這個之後就可以來算$S[L,...,R]$是否可以在第$k+1$層時刪除了。我們從$S[L]$開始往右邊掃，當遇到$S[i]$時，一個決策是：選一個$r$使得$S[i,...,r]$可以被刪除，那麼轉移到$S[r+1]$的狀態。另一個決策則是將$S[i]$放進一個「暫存字串」中，轉移到$S[i+1]$，並且我們想要在處理完$S[R]$時暫存字串是可以一次被刪除的（就和前面的條件等價了）。因此我們可以用一個 trie 節點搭配當前的 index 來做 DP 狀態，設 $dp[x][i]$ 代表只考慮字串$S[L,...,i]$時，是否可以讓「暫存字串」在 trie 上的節點為$x$，這樣就可以$O(1)$轉移了，總複雜度為$O(n^5)$。

code :

[HOJ 123][TIOJ 1810] 漫遊小鎮 / 小鎮DP

作法：

這題是標準的插頭DP題，需要把連通性壓入狀態表示中，在上一篇中提到的是簡單的版本。因為那題只要求用多個哈密頓圈覆蓋，而這題則是限定用一條哈密頓鍊覆蓋。另外還有要求是從左上角走到左下角，因此這時候能拼的拼圖總共有9種：

其中上面三種只能拼在左上角和左下角，並且左上角和左下角一定要用這三種拼圖來拼。但兩題不只有差這樣而已，如果一樣直接DP的話，$n=3$ 時會得出答案為 $3$ （多出來的路徑就是下面的左圖）。也就是在DP最後一格時，誤把同一個連通分量的兩條線接起來了。

左圖和右圖的情形在狀態表示中都是$0011$，但左圖的情形不能轉移，右圖的情形則可以，因此這樣的狀態表示會造成誤判，必須細分。所以此時只好把線的「連通性」納入狀態表示中，也就是在左圖的$0011$中，其實兩個$1$是連通的，而右圖的$0011$的兩個$1$則是不連通的。所以此時我們要想辦法把連通性壓入狀態中。對於一個狀態中的$1$代表的那條線來說，如果沿著他往回走，那麼有幾種可能：一種是走回這個狀態表示中的另外一個$1$，一種是走回左上角，一種是走回左下角。而「走回左下角」的情形在還沒有轉移左下角那格之前是不存在的。而轉移到左下角那格之前每個狀態會恰有一個$1$代表從左上角走過來的線。因此我們就可以用以下的方法表示狀態：如果這格的線是走回左上或左下角的，那麼就把這格位子的值設為$1$，而如果是走回這個狀態的另一條線的情形，就把這一對連通的線的值都設為$2$，如果有第三組就設為$3$，以此類推。這樣因為$n\leq 10$（TIOJ的數字範圍），也就是一個狀態最多有$11$個位子，用到最多數字的情形是類似$12233445566$的樣子，因此我們可以用$7$進制來表示一個儲存了連通訊息的狀態（當然沒有線的話就是$0$）。（註：事實上用$8$進制會更快，在編碼解碼的過程可以用位元運算加速。）

但這樣的表示還不夠，因為可能有很多重複的狀態，例如$12233000$和$13322000$兩個是一模一樣的狀態，所以對每個狀態我們可以把他「標準化」，把他改成「在所有其他和他等價的狀態表示中字典序最小的狀態表示法」，這只要$O(n)$掃過去就可以做到了，細節在此省略（這東西好像叫作最小表示法）。這樣可以用排列組合稍微算一下，會得到一個階段中的節點數量最多只會有幾萬個，再乘上$n^2$得到總狀態數最多幾百萬，還在可以接受的範圍內（好像還有一種表示法叫括號表示法，不過我還沒研究）。

有了狀態表示法後，轉移的部份也蠻麻煩的。首先當然要滿足不能在邊界放有線撞到邊界的拼圖，還有兩塊拼圖之間必須同時有線或無線。假設現在在轉移某個格子的某個狀態，記當前格的左邊界的狀態值為$x$，上邊界的狀態值為$y$，那麼會分成好幾種可能：

1. $x=y=0$
2. $x=0 , y\neq 0$
3. $x\neq 0,y=0$
4. $x,y\neq 0$

因為 2. 和 3. 幾乎一樣，所以等等就略過 3 的討論。對於 1. 來說，勢必要鋪上 ┏ 這塊拼圖，而轉移後的狀態的計算方法可以先在對應的兩個位子填上$7$，然後進行一次標準化得到。對於 2. 來說，可以鋪上 ┃ 和 ┗ 這兩種拼圖，而新的狀態就只要把對應的位子改成$y$就可以了，並且不用重新標準化。4. 則是最麻煩的，這時必須要放上 ┛ 。首先當 $x=y$ 時不可以放，否則就會把已經連通的分量再連起來，形成一個圈。但有個特例要判，就是如果當前格是右下角的話，那麼就可以轉移了，因為此時是把兩個$1$連起來，才能形成最後的一條哈密頓鍊。至於$x\neq y$時又分成幾種情形，如果$x=1$的話，當放上了這塊拼圖之後，另外一個值為$y$的位置就會變成$1$，因為這時候那條線就變成可以走到左上（或左下）角了，同理如果$y=1$的話，則是另一個值為$x$的位置要換成$1$。如果是$x$和$y$都不為$1$，那麼這時候就把$x$和$y$的另一個位置的值都改成同一個數就可以了。以上這些屬於 4. 的情形都必須要重新標準化一次。

實作方法有很多種，一種是預先編碼，把每種狀態都和一個$id$值對應，那麼就可以用$dp[i][j][k]$代表當前格是$(i,j)$，並且此時為第$k$個狀態的方法數，但這樣會有很多無效的狀態。我寫的方法則是直接把$dp$陣列改成 map，用壓縮過後的七進制的那個數字直接當成狀態的 index ，這樣可以在一邊DP時把新的有效的狀態加入 map 裡，不會有無效的狀態在裡面。不過不管是用哪種方法，都必須要寫兩個函式對一個$7$（或$8$）進制的數做編碼和解碼。

最後，這裡也有關於插頭DP的文章，寫的很詳細，不過我還沒全部看完@@

code :

[TIOJ 1692] Problem B 道路巡邏問題

作法：

原始求尤拉路徑(迴路)的DFS演算法是：從一個奇點(如果沒有的話就從隨便一個點)DFS，走到一個不能再走的點之後就沿著走過來的邊們走回去，這樣就得到一條尤拉路徑了。但如果直接套用會爛掉，因為他可能不只有兩個奇點，所以有可能找到的路徑不是好好接起來的。

我的作法是當走到一個點不能再走時就一路 return 回去，這樣會找到好幾條鏈和好幾個圈，但這樣不一定會讓路徑數最少，所以就試著把環都黏到一條鏈上，因為如果一條鏈上經過的點和一個圈上經過的點有交集的話，那麼就可以把兩者黏起來變成一條鏈。所以就對每個圈，枚舉他是否可以黏到一條鏈上。另外也有可能有兩個圈共用一個點，所以還有要試任兩個圈能不能黏起來。

後來想想應該有更簡單的作法，例如把所有奇點都連一條到虛擬節點 0 的邊，然後對他求尤拉路之類的應該會比較好寫，但是我沒有仔細想XD。

code :

#include<bits/stdc++.h>
#include"lib1692.h"
using namespace std;
const int maxn=1000+10,maxm=50000+10 ;
struct P{int x,y ;};
vector<P> edge ;
vector<int> v[maxn] ;
 
struct path{ vector<int> p ; int st,ed ; } v1[2*maxm],v2[2*maxm] ;
int cnt1=0,cnt2=0 ;
 
int E[maxn] ;
bool vis[maxm] ;
void dfs(int x,int t)
{
    for(int &i=E[x];i<v[x].size();i++) if(!vis[v[x][i]])
    {
        vis[v[x][i]]=1 ;
        int to= (edge[v[x][i]].x==x ? edge[v[x][i]].y : edge[v[x][i]].x) ;
        int tmp=v[x][i] ;
        dfs(to,t) ;
 
        if(t==1) v1[cnt1].p.push_back(tmp) ;
        else v2[cnt2].p.push_back(tmp) ;
 
        return ;
    }
 
    if(t==1) v1[cnt1].st=x ;
    else v2[cnt2].st=x ;
}
 
bool used[maxn] ;
bool merge(path &a,const path &b)
{
    memset(used,0,sizeof(used)) ;
    for(auto i : a.p) used[edge[i].x]=used[edge[i].y]=1 ;
    int st=-1 ;
    for(auto i : b.p) if(used[edge[i].x])
        { st=edge[i].x ; break ; }
    if(st==-1) return 0 ;
 
    int sz1=a.p.size() , sz2=b.p.size() ;
    a.p.resize(sz1+sz2) ;
 
    int id1=0 ;
    if(a.st==st) id1=-1 ;
    else for(int now=a.st;;id1++)
    {
        int to= ( edge[a.p[id1]].x==now ? edge[a.p[id1]].y : edge[a.p[id1]].x ) ;
        if(to==st) break ;
        now=to ;
    }
 
    for(int i=id1+1;i<sz1;i++) a.p[i+sz2]=a.p[i] ;
 
    int id2=0 ;
    for(int now=b.st;;id2++)
    {
        int to= ( edge[b.p[id2]].x==now ? edge[b.p[id2]].y : edge[b.p[id2]].x ) ;
        if(to==st)
        {
            for(int i=id2+1;i<id2+1+sz2;i++)
                a.p[i-id2+id1]=b.p[i%sz2] ;
            break ;
        }
        now=to ;
    }
    return 1 ;
}
 
main()
{
//    freopen("pB.2.in","r",stdin) ;
    Init() ;
    int n,m ; GetVE(n,m) ;
    for(int i=0;i<m;i++)
    {
        int x,y ; Get(x,y) ;
        edge.push_back((P){x,y}) ;
        v[x].push_back(i) ;
        v[y].push_back(i) ;
    }
    for(int i=1;i<=n;i++) if(v[i].size()%2)
    {
        for(int &j=E[i];j<v[i].size() && vis[v[i][j]];j++) ;
        if(E[i]>=v[i].size()) continue ;
        dfs(i,1) ;
        v1[cnt1++].ed=i ;
    }
    for(int i=1;i<=n;i++)
    {
        for(int &j=E[i];j<v[i].size() && vis[v[i][j]];j++) ;
        if(E[i]>=v[i].size()) continue ;
        v2[cnt2].st=-1 ;
        dfs(i,2) ;
        v2[cnt2++].ed=i ;
    }
 
    for(int i=0;i<cnt2;i++) for(int j=0;j<cnt1;j++)
        if(merge(v1[j],v2[i]))
    {
        for(int k=i;k<cnt2-1;k++) v2[k]=v2[k+1] ;
        cnt2-- ; i-- ;
        break ;
    }
 
    for(int i=0;i<cnt2;i++) for(int j=i+1;j<cnt2;j++)
        if(merge(v2[i],v2[j]))
    {
        for(int k=j;k<cnt2-1;k++) v2[k]=v2[k+1] ;
        cnt2-- ; j-- ;
        if(i>=cnt2) break ;
    }
 
    for(int i=0;i<cnt1;i++)
    {
        ReportVst(v1[i].st) ;
        for(auto j : v1[i].p) ReportE(j+1) ;
        ReportVed(v1[i].ed) ;
    }
    for(int i=0;i<cnt2;i++)
    {
        ReportVst(v2[i].st) ;
        for(auto j : v2[i].p) ReportE(j+1) ;
        ReportVed(v2[i].ed) ;
    }
    Final() ;
}
 
 

[TIOJ 1698] Problem H 神殿裡的觸手

作法：

考慮 Kruskal 的過程，假設現在邊權 < k 的邊都加入了，形成了好幾坨連通塊，現在看看所有邊權等於 k 的邊，如果他的兩端點在同一個連通塊那他絕對不會選到。我們要找的是一定會被選到的邊，所以如果一張新的圖，先把每個所有聯通塊縮起來當成一坨點，然後對於一條邊權 = k 的邊，如果他的兩端點在不同的連通塊上，就在新的圖裡的兩坨點之間建一條邊，這樣就可以得到必須出現在MST裡的邊就會是這張圖裡的橋。如果是橋的話顯然一定要，而如果不是的話，代表把這條邊拔掉之後剩下的邊還是可以讓該連的連起來。在實作上，因為當我們把邊權 = k 的邊都跑過一次之後，就知道等一下在找橋的時候會用到那些頂點了，所以可以不用每次換一個邊權作橋的時候都把所有的要作橋的圖清乾淨。還要注意到所有的邊都要跑到，而新的圖不一定整個連通，所以還必須多紀錄新的圖中到底有哪些頂點，要確保所有的新圖裡的頂點連出的邊都要被走到。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxm=400000+10 ;
struct P
{
    int x,y,dis,id ;
    bool operator < (const P &rhs) const
    {
        return dis<rhs.dis ;
    }
};
 
struct Q{int x,y;};
 
vector<P> E ;
 
int fa[maxn] ;
int getfa(int x)
{
    return fa[x]==x ? x : fa[x]=getfa(fa[x]) ;
}
 
bool ans[maxm] ;
int ver[maxm],cnt ;
int eid[maxm] ;
vector<Q> edge ;
vector<int> v[maxn] ;
bool vis[maxn],evis[maxm] ;
int lev[maxn] ;
 
int dfs(int x,int l)
{
    int low ;
    lev[x]=low=l ;
    vis[x]=1 ;
    for(auto i : v[x]) if(!evis[i])
    {
        evis[i]=1 ;
        int to= edge[i].x==x ? edge[i].y : edge[i].x ;
        if(vis[to]) low=min(low,lev[to]) ;
        else
        {
            int tmp=dfs(to,l+1) ;
            low=min(low,tmp) ;
            if(tmp > lev[x]) ans[eid[i]]=1 ;
        }
    }
    return low ;
}
 
void Kruskal()
{
    sort(E.begin(),E.end()) ;
    for(int i=0;i<E.size();)
    {
        cnt=0 ;
        edge.clear() ;
        int j ;
        for(j=i;j<E.size() && E[j].dis==E[i].dis;j++) ;
        for(int k=i;k<j;k++)
        {
            int x=getfa(E[k].x) , y=getfa(E[k].y) ;
            if(x==y) continue ;
            ver[cnt++]=x ; ver[cnt++]=y ;
            v[x].clear() ; v[y].clear() ;
            vis[x]=vis[y]=0 ;
        }
        for(int k=i;k<j;k++)
        {
            int x=getfa(E[k].x) , y=getfa(E[k].y) ;
            if(x==y) continue ;
 
            edge.push_back((Q){x,y}) ;
            int sz=edge.size() ;
            v[x].push_back(sz-1) ;
            v[y].push_back(sz-1) ;
            eid[sz-1]=E[k].id ;
            evis[sz-1]=0 ;
        }
 
        for(int k=0;k<cnt;k++) if(!vis[ver[k]])
            dfs(ver[k],0) ;
 
        for(int k=i;k<j;k++) fa[getfa(E[k].x)]=getfa(E[k].y) ;
        i=j ;
    }
}
 
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n;i++) fa[i]=i ;
    for(int i=0;i<m;i++)
    {
        int x,y,dis ; scanf("%d%d%d",&x,&y,&dis) ;
        E.push_back((P){x,y,dis,i+1}) ;
    }
    Kruskal() ;
    int num=count(ans+1,ans+m+1,true) ;
    printf("%d\n",num) ;
    if(!num) printf("0\n") ;
    else for(int i=1;i<=m;i++) if(ans[i]) printf("%d%c",i,(--num)?' ':'\n') ;
}
 

[TIOJ 1691] Problem A 圍籬架設問題

作法：

兩個子序列一定有一個位置不一樣，那麼大概可以想到兩個子序列的前後一定是一整排一樣的東西，只有中間一點點不一樣。其實只要找到 i 和 j 使得 a[ i ] = a[ j ] 且 i != j ，那麼考慮第一個子序列取 a[ 1 ] ~ a[ i ] , a[ j + 1 ] ~ a[ n ] ，第二個子序列取 a[ 1 ] ~ a[ i - 1 ] , a[ j ] ~ a[ n ] ，就可以得到其中一組解，並且可以知道最佳解一定長成這樣，所以只要找到 j - i 最小且 a[ j ] = a[ i ] 的 j - i 的值就好了。

code :

#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
 
map<int,vector<int> > mp ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
    {
        int x  ; scanf("%d",&x) ;
        mp[x].push_back(i) ;
    }
    int mi=n ;
    for(auto i : mp) for(int j=0;j<(int)i.S.size()-1;j++)
        mi=min(mi,i.S[j+1]-i.S[j]) ;
    printf("%d\n",n-mi) ;
}
 

[TIOJ 1837][IOI 2013] ArtClass

作法：

總之就是亂做一通 + 經過別人的提示才過的。我一開始還在想判白色區塊和黑色區塊的格子數，後來發現不行，改成判白色區塊和黑色區塊的最大矩形，後來發現也會爛掉。最後是改成看每個點和他的四個相鄰點，去計算有幾組相鄰點的顏色差到了某個程度以上，這樣可以成功把第二種圖和第三種圖分出來，因為第三種圖是最多的，第二種圖大概也有 1/4 ，剩下第一種和第四種要再分。

後來聽別人分第一種和第四種的方法是，去看有多少組相鄰點的顏色相差很多，第四種圖的組數會比第一種圖的少，但他們之間的分界我亂試了很久才過，還有判斷顏色相差很多的函式和判斷顏色是否一樣的函式我也是亂做的，後來得到的準確率好像是 90.3% ，總之就是亂寫過了。

另外，何達睿的作法是看每一個橫排的亂七八糟度(?)，code 附在下面，比我的簡潔好多QQ。還有周逸的作法是在多考慮綠色的多少，好像是看平方和之類的，如果特別多那就是第二種圖，沒有詳細聽他講，結果他就把我的CBD大頭貼判成第二種圖( 印象派風景畫 )了XDD

code :

#include<bits/stdc++.h>
#define DB double
#define MAX(x,y,z) max(x,max(y,z))
#define ADD(x,y,z) (x+y+z)
using namespace std;
const int maxn=1000 ;
 
int ABS(int x)
{
    return x>0 ? x : -x ;
}
 
int a[maxn][maxn][3] ;
bool same(int x1,int y1,int x2,int y2)
{
    int x=0 ;
    for(int i=0;i<3;i++)
    {
        x+=ABS(a[x1][y1][i]-a[x2][y2][i]) ;
        if(ABS(a[x1][y1][i]-a[x2][y2][i])>10) return 0 ;
    }
    return 1 ;
}
 
int dif(int x1,int y1,int x2,int y2)
{
    return ADD(ABS(a[x1][y1][0]-a[x2][y2][0]),
               ABS(a[x1][y1][1]-a[x2][y2][1]),
               ABS(a[x1][y1][2]-a[x2][y2][2])) ;
}
 
int n,m ;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1} ;
 
int solve()
{
    int cnt=0 ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        for(int k=0;k<4;k++)
    {
        int nx=i+dx[k] , ny=j+dy[k] ;
        if(nx<0||nx>=n||ny<0||ny>=m) continue ;
        if(!same(i,j,nx,ny)) cnt++ ;
    }
 
    DB ans=cnt*100.0/4.0/n/m ;
    if(ans>=64.0) return 3 ;
    if(ans>=21.0) return 2 ;
 
    cnt=0 ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        for(int k=0;k<4;k++)
    {
        int nx=i+dx[k] , ny=j+dy[k] ;
        if(nx<0||nx>=n||ny<0||ny>=m) continue ;
        if(dif(i,j,nx,ny)>180) cnt++ ;
    }
    if(cnt>7000) return 1 ;
    return 4 ;
}
 
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<n;i++) for(int j=0;j<m;j++)
            scanf("%d%d%d",&a[i][j][0],&a[i][j][1],&a[i][j][2]) ;
        printf("%d\n",solve()) ;
    }
}

看橫排的亂七八糟度的 code :

http://imgur.com/YCz2qBF

[TIOJ 1689][USACO 2009 Gold] 安全路徑 Safe Travel

作法：

這題是我去查解才會的，做法和這個網站一樣。
總之就是先建出最短路徑樹，那麼對每個點來說走到他但不能經過的邊就是他連他老爸的邊，所以對每個點 u ，答案的走法一定會長的像「先從根走到一個點 v (路上不能經過 u )」，然後跳到 u 的子樹( 含 u )，然後再往上沿樹邊走到 u ( 或如果跳到 u 就不走 )，這件事可以由「因為他是最短路徑樹」直接得到。所以和那個網站講的一樣，對每個節點 u 維護一個 priority queue ，裡面放的值是 ( x , val ) ，其中 x 是 u 的一個子節點，且 x 可沿著非樹邊走到 v ， val 就存 dist[ x ] + dist[ v ] + dis[ x ][ v ] ，其中 dist 代表每個點到根的最短距離，這樣我需要的值就是 priority queue 裡面的 val 最小的數，再減掉 dist[ u ] 就可以了。合併的部分我是用啟發式合併，左偏樹聽起來太恐怖了。

另外，如果 priority queue 的 top ，假設叫 ( x , val ) 好了，那麼如果 x 是當前節點 u 的子孫，那這條邊就是不合法的，必須要 pop 掉，一直 pop 到可以用的邊就好了。並且如果一條邊在我們做到節點 u 的時候他就被 pop 掉了，那麼在做 u 的祖先的時候，這條邊對 u 的祖先們一定也是不合法的邊( 因為從根走到 x 會經過 u ，這就代表了會經過 u 的每個祖先 )。

code :

#include<bits/stdc++.h>
#define INF 1000000000
using namespace std;
const int maxn=100000+10 ;
struct P{int to,dis;};
struct Q
{
    int id,dis ;
    bool operator < (const Q &rhs) const
    {
        return dis>rhs.dis ;
    }
};
 
vector<P> v[maxn] ;
vector<int> v2[maxn] ;
int fa[maxn] ;
int n,d[maxn] ;
bool done[maxn] ;
priority_queue<Q> pq ;
 
void Dijkstra(int st)
{
    fill(d+1,d+n+1,INF) ;
    d[st]=0 ; pq.push((Q){st,0}) ;
    while(!pq.empty())
    {
        Q u=pq.top() ; pq.pop() ;
        if(done[u.id]) continue ;
        done[u.id]=1 ;
        if(u.id!=st) v2[fa[u.id]].push_back(u.id) ;
        for(auto i : v[u.id]) if(d[i.to] > d[u.id]+i.dis)
        {
            fa[i.to]=u.id ;
            d[i.to]=d[u.id]+i.dis ;
            pq.push((Q){i.to,d[i.to]}) ;
        }
    }
}
 
int in[maxn],out[maxn],t=0 ;
void dfs0(int x)
{
    in[x]=++t ;
    for(auto i : v2[x]) dfs0(i) ;
    out[x]=++t ;
}
 
bool is_fa(int x,int y) /** x is fa of y , x = y -> return true */
{
    return in[x]<=in[y] && out[x]>=out[y] ;
}
 
int ans[maxn] ;
priority_queue<Q> pq2[maxn] ;
int id[maxn] ;
 
int merge(int x,int y)
{
    if(pq2[x].size()<pq2[y].size()) swap(x,y) ;
    while(!pq2[y].empty())
        pq2[x].push(pq2[y].top()) , pq2[y].pop() ;
    return x ;
}
 
void dfs1(int x)
{
    id[x]=x ;
    for(auto i : v2[x]) dfs1(i) , id[x]=merge(id[x],id[i]) ;
    for(auto i : v[x]) if(i.to!=fa[x])
        pq2[id[x]].push((Q){i.to,d[i.to]+d[x]+i.dis}) ;
    while(!pq2[id[x]].empty() && is_fa(x,pq2[id[x]].top().id)) pq2[id[x]].pop() ;
    ans[x]= pq2[id[x]].empty() ? -1 : (pq2[id[x]].top().dis - d[x]) ;
}
 
main()
{
    int m ; scanf("%d%d",&n,&m) ;
    while(m--)
    {
        int x,y,dis ; scanf("%d%d%d",&x,&y,&dis) ;
        v[x].push_back((P){y,dis}) ;
        v[y].push_back((P){x,dis}) ;
    }
    Dijkstra(1) ;
    dfs0(1) ;
    dfs1(1) ;
    for(int i=2;i<=n;i++) printf("%d\n",ans[i]) ;
}