#include <cstdio>
#include <queue>

using namespace std;

const int nmax = 50000;
const int mmax = 250000;

int dest[1+mmax],urm[1+nmax],last[1+nmax],c[1+mmax],sol[1+nmax];

bool check[1+nmax];

struct Point
{
    int x,cost;
};

bool operator< (const Point &a,const Point &b)
{
    return a.cost > b.cost;
}

priority_queue <Point> h;

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= m; i ++)
    {
        int x,y;
        scanf("%d %d %d",&x,&y,&c[i]);
        dest[i] = y;
        urm[i] = last[x];
        last[x] = i;
    }
    h.push( {1,0});
    check[1] = 1;
    while(h.size() > 0)
    {
        Point s = h.top();
        h.pop();
        int muc = last[s.x];
        sol[s.x] = s.cost;
        while(muc != 0)
        {
            if(check[dest[muc]] == 0)
            {
                h.push( {dest[muc],s.cost + c[muc]});
                check[dest[muc]] = 1;
            }
            muc = urm[muc];
        }
    }
    for(int i = 2;i <= n;i ++)
        printf("%d ",sol[i]);
        return 0;
}