#include <iostream>
#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;
vector< ii > G[NMAX];
int dist[NMAX];
int viz[NMAX];
int A_node[NMAX], A_dist[NMAX];
int sz;

inline int pop_node()
{
    if (sz == 0)
        return 0;

    int idx = 1;
    int ret = A_node[1];
    A_node[1] = A_node[sz];
    A_dist[1] = A_dist[sz];
    --sz;

    while (idx*2 <= sz)
    {
        int fiu;
        if (idx*2+1 < sz && A_dist[idx*2+1] < A_dist[idx*2])
            fiu = 1;
        else
            fiu = 0;

        if (A_dist[idx] > A_dist[idx*2+fiu])
        {
            swap(A_node[idx], A_node[idx*2+fiu]);
            swap(A_dist[idx], A_dist[idx*2+fiu]);
        }
        idx = 2*idx + fiu;
    }

    return ret;
}

inline void push_node(int node, int d)
{
    int idx = ++sz;
    A_node[idx] = node;
    A_dist[idx] = d;

    while (idx>1 && A_dist[idx/2] > A_dist[idx])
    {
        swap(A_dist[idx/2], A_dist[idx]);
        swap(A_node[idx/2], A_node[idx]);
        idx /= 2;
    }
}

void dijkstra()
{
    dist[1] = 0;
    FORIE(i,2,N)
        dist[i] = INF;
    sz = 0;

    push_node(1, 0);

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

                if (dist[next] > dist[node] + G[node][i].second)
                {
                    dist[next] = dist[node] + G[node][i].second;
                    push_node( next, dist[next]);
                }
            }

        viz[node] = true;
    }

}

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

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

    //cin >> N >> M;

    FOR(i,M)
    {
        int x,y,c;
        char s[100];
        gets(s);
        sscanf(s, "%d %d %d", &x, &y, &c);
        //cin >> x >> y >> c;
        G[x].PB( MP(y,c) );
    }

    dijkstra();

    FORIE(i,2,N)
        if (dist[i] != INF)
            printf("%d ", dist[i]);
            //cout << dist[i] << " ";
        else
            printf("0 ");
            //cout << "0 ";

    //cout << "\n";

    printf("\n");

    return 0;
}