#include <cstdio>
#include <queue>
#include <vector>
#define Nmax 50005
#define INF 2000000000

using namespace std;

int dp[Nmax];

struct edge
{
    int cost,nod;
};
vector <edge> L[Nmax];

struct nr
{
    int val;
    bool operator <(const nr A) const
    {
        return dp[val]>dp[A.val];
    }
};
priority_queue <nr> Q;

inline void Dijkstra()
{
    nr w;
    int nod;
    vector <edge>::iterator it;
    w.val=1; Q.push(w);
    while(!Q.empty())
    {
        w=Q.top(); nod=w.val; Q.pop();
        for(it=L[nod].begin();it!=L[nod].end();++it)
            if(dp[it->nod]>dp[nod]+it->cost)
            {
                dp[it->nod]=dp[nod]+it->cost;
                w.val=it->nod;
                Q.push(w);
            }
    }
}

int main()
{
    int i,N,x,y,z,M;
    edge w;
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);
    scanf("%d%d", &N,&M);
    while(M--)
    {
        scanf("%d%d%d", &x,&y,&z);
        w.nod=y; w.cost=z;
        L[x].push_back(w);
    }
    for(i=2;i<=N;++i)
        dp[i]=INF;
    Dijkstra();
    for(i=2;i<=N;++i)
        if(dp[i]==INF)
            printf("0 ");
        else
            printf("%d ", dp[i]);
    printf("\n");
    return 0;
}