#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});
    while(h.size() > 0)
    {
        Point s = h.top();
        h.pop();
        if(check[s.x] == 0)
        {
            int muc = last[s.x];
            check[s.x] = 1;
            sol[s.x] = s.cost;
            while(muc != 0)
            {
                if(check[dest[muc]] == 0)
                {
                    h.push( {dest[muc],s.cost + c[muc]});
                }
                muc = urm[muc];
            }
        }
    }
    for(int i = 2; i <= n; i ++)
        printf("%d ",sol[i]);
    return 0;
}