#include<cstdio>
#include<queue>
#define oo 0x3f3f3f3f
#define DIM 8192
using namespace std;


char ax[DIM+16];
int pz;

inline void cit(int &x)
{
            x=0;
            while((ax[pz]<'0' || ax[pz]>'9') && (ax[pz]!='-'))
                        if(++pz==DIM)fread(ax, 1, DIM, stdin), pz=0;

            int neg=0;
            if(ax[pz]=='-')
            {
                        neg=1;
                        if(++pz==DIM)fread(ax, 1, DIM, stdin),pz=0;
            }

            while(ax[pz]>='0' && ax[pz]<='9')
            {
                        x=x*10+ax[pz]-'0';
                        if(++pz==DIM)fread(ax,1, DIM, stdin),pz=0;
            }
            if(neg) x=-x;
}


struct node
{
    int nd;
    int cost;
    node *next;
};

node *list[50001];
int d[50001], a[50001], n, m;

struct cmp
{
    bool operator()(const int &a, const int &b)const
    {
        if(d[a] > d[b]) return 1;
        return 0;
    }
};

void read()
{
    scanf("%d %d", &n, &m);

    int x, y, z;
    for ( int i = 1; i <= m; ++i )
    {
        //scanf("%d %d %d", &x, &y, &z);
        cit(x);
        cit(y);
        cit(z);
        node *q = new node;
        q->nd = y;
        q->cost = z;
        q->next = list[x];
        list[x] = q;
    }
}

void dijkstra()
{
    priority_queue<int, vector<int>, cmp> Q;

    memset(d, oo, sizeof(d));

    d[1] = 0;
    Q.push(1);


    while(!Q.empty())
    {
        int u = Q.top();
        Q.pop();
               node *q = list[u];

                while ( q )
                {
                    if ( d[q->nd] > d[u] + q->cost )
                    {
                        d[q->nd] = d[u] + q->cost;
                        Q.push(q->nd);
                    }
                    q = q->next;
                }

    }

    freopen("dijkstra.out","w",stdout);
    for(int i = 2; i <= n; ++i)
        printf("%d ", d[i] == oo ? 0 : d[i]);

}

int main()
{
    freopen("dijkstra.in","r",stdin);
    read();
    dijkstra();
    return 0;
}