#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define inf 1<<30
#define NMax 50005
using namespace std;

typedef pair<int,int> VP;
vector<VP> vc[NMax];
int d[NMax],viz[NMax];

priority_queue<VP, vector<VP>, greater<VP> > Q;

int main ()
{
    int n,m,i,a,b,c,nod,dist;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        vc[a].push_back(make_pair(b,c));
    }
    for (i=2; i<=n; i++)
        d[i]=inf;
    Q.push(make_pair(0,1));
    while (!Q.empty())
    {
        while (!Q.empty() && viz[Q.top().second])
            Q.pop();
        if (Q.empty())
            break;

        dist=Q.top().first;
        nod=Q.top().second;
        Q.pop();
        viz[nod]=1;

        vector<VP>::iterator it;
        for (it=vc[nod].begin(); it!=vc[nod].end(); ++it)
            if (d[it->first]>dist+it->second)
            {
                d[it->first]=dist+it->second;
                Q.push(make_pair(d[it->first],it->first));
            }
    }
    for (i=2; i<=n; i++)
        printf("%d ",(d[i]!=inf) ? d[i] : 0);
    return 0;
}