#include <cstdio>
#include <vector>
#include <set>

using namespace std;

typedef long long LL;
typedef vector<int> vi;
typedef vector< vi > vii;
typedef vector<string> vs;
typedef vector<double> vd;
typedef pair<int, int> ii;
#define PB push_back
#define SZ(v) v.size()
#define MP(x, y) make_pair((x), (y))
#define ALL(v) (v).begin(), (v).end()
#define FORIT(i,c) for (typeof((c).end()) i=(c).begin(); i!=(c).end(); ++i)
#define FOR(i,n) for (int i = 0; i<(n); ++i)
#define FORE(i,n) for (int i = 0; i<=(n); ++i)
#define FORI(i,n1,n2) for (int i = n1; i<(n2); ++i)
#define FORIE(i,n1,n2) for (int i = n1; i<=(n2); ++i)
#define FORV(i,v) for (unsigned int i = 0; i<SZ(v); ++i)

#define INF 0x3f3f3f3f
#define EPS 1e-9

#define NMAX 50001

int N,M;
vi G[NMAX];
vi D[NMAX];
int dist[NMAX];
int viz[NMAX];

void dijkstra()
{
    set< ii > Q;

    dist[1] = 0;
    FORIE(i,2,N)
        dist[i] = INF;

    Q.insert( MP(0, 1) );

    while (!Q.empty())
    {
        set< ii >::iterator it = Q.begin();

        int node = (*it).second;

        if (!viz[node])
        FORV(i, G[node])
        {
            int next = G[node][i];

            if (dist[next] > dist[node] + D[node][i])
            {
                dist[next] = dist[node] + D[node][i];
                Q.insert( MP(dist[next], next) );
            }
        }

        viz[node] = true;
        Q.erase(it);

    }



}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%d %d", &N, &M);

    FOR(i,M)
    {
        int x,y,c;
        scanf("%d %d %d", &x, &y, &c);
        G[x].PB(y);
        D[x].PB(c);
    }

    dijkstra();

    FORIE(i,2,N)
        printf("%d ", dist[i]);

    return 0;
}