#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int a[101][101], n, m, v[101], d[101];

int main()
{
    int i, j, k;
    fin >> n >> m;

    for(i = 1; i <= m; i++){
        int A, B, C;
        fin >> A >> B >> C; a[A][B] = C;
    }

    for(i = 1; i <= n; i++){
        d[i] = a[1][i];
    }

    v[1] = 1; d[0] = 0X3F3F3F3F;

    for(k = 1; k < n; k++){
        int pmax = 0;

        for(i = 1; i <= n; i++){
            if(v[i] == 0 && d[i] < d[pmax]){
                pmax = i;
            }
        }

        if(pmax > -1){
            v[pmax] = 1;
            for(i = 1; i <= n ; ++i)
                if(v[i] == 0 && d[i] > d[pmax] + a[pmax][i])
                    d[i] = d[pmax] + a[pmax][i];
        }
    }

    for(i = 2; i <= n; i++){
        fout << d[i] << " ";
    }
}




//hamiltonian
//dp[mask][j] = drum de cost minim care contine el. din mask si se tremina in j
//dp[1][1] = 0
//dp[(1 << n) - 1][j] + arc[j][1]

//dp[mask][j] = min(dp[mask + (1 << k)][k] + arc[j][k] | mask & (1 << k)) == 0, arc[j][k]


//sobo
//dp[mask] = costul minim sa aflam sobolanul destept, daca stim ca este unul din mask
//ans[p] = 0 = masca a soblanilor care au bitul p = 1
//daca raspunsul la intrebare p este 0, atunci ne vom uita in ((1 << n) - 1)^ans[p]
//dp[mask]

//-pt fiecare intrebare, rezultatul in cazul ala
//ask[p]
//dp[mask] = min(ask[p])
//ask[p] = max(dp[mask&ans[p]]), dp[mask&(((1 << n)- 1) ^ ans[p]))] + cost[p]


//love-hate




//#3508 Bal

//dp[mask] = nr de moduri de a cupla baietii din mask cu primele popcount[mask] fete

//l = popcount(mask)

//for(k = 0; k < n; k++){
    //if(mask & (1 << k)) continue;
 //  if(mat[1][k] == 0)continue;
  //  dp[mask | (1 << k)] += dp[mask];
//}



//505
//dp[i][mask] = nr maxim de operatii daca consideram primrle i coloane, si pe coloana i avem mask
//dp[i][mask] = min(dp[i - 1][mask2 | good(mask2, mask)]) + pop_count(mask ^ maski)


//harmony
//dp[i][mask] = rez optim pt primele i elemente si factori primi doar cei din mask
//fact[k] = masca factorilor primi din k
//cnt = factori primi

//for(i = 1; i <= n; i++){
  //  for(mask = 0; mask < 1 << cnt; mask++){
    //    for(k = 1; k < 60; k++){
      //      if(mask & k != k) continue;
        //    dp[i][mask] = min(dp[i][mask], dp[i - 1][mask ^ fact[k]] + abs(a[i] - k));
    //    }
  //  }
//}


//poly
//dp[i][mask] = subsir maxim daca consideram primele i elemente, si ultimele elemente din subsir are mask factori primi
//dp[i][mask] = max(dp[i - 1][mask2] + 1) | mask1 & mask2 == 0
// mask & mask2 == 0, inseamna ca mask2 & (~mask) == mask2

//SOSdp[i][mask]
//dp[i][mask] = max(dp[i - 1][mask], SOSdp[i - 1][~mask] + 1)
//m = 7
//O(N*(2^m + m * 2 ^ m))
//O(N * (2^m * 2^m))


//cast
//dp[i][mask] = timpul minim de a trimite la toate nodurile din mask, daca aincepem cu i, mask fixat, luam j si submask
//dp[i][mask] = min(dp[i][mask], max(dp[j][submask], dp[i][mask^submask]) + cost[i][j])



//bit prblem