#include <vector>
#include <cstdio>
#include <set>
using namespace std;

#define INF 100000000

int d[50001],n,m;
set < pair<int,int> > T;
vector <int> nod[50001];
vector <int> cost[50001];


int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    int a, b, c;
    for(int k=2;k<=n;k++)
        d[k]=INF;
    for(int k=1;k<=m;k++)
    {
        scanf("%d %d %d",&a,&b,&c);
        nod[a].push_back(b);
        cost[a].push_back(c);
    }
    T.insert(make_pair(0,1));
    while(T.size()>0)
    {
        a=(*T.begin()).first;
        b=(*T.begin()).second;
        T.erase(*T.begin());

        for(int k=0;k<nod[b].size();k++)
            if(d[nod[b][k]] > d[b] + cost[b][k])
            {
                d[nod[b][k]] = d[b] + cost[b][k];
                T.insert(make_pair(d[nod[b][k]],nod[b][k]));
            }
    }
    for(int k=2;k<=n;k++)
        if(d[k]==INF)
            printf("0 ");
        else
            printf("%d ",d[k]);
    return 0;
}