#include <cstdio>
#include <queue>
#include <vector>

#define vv 50001
#define INFI 0x3f3f3f3f

using namespace std;

vector <int> v[vv],c[vv];
queue <int> q;
int n,m,a[vv],viz[vv];

void bellman_ford()
{
    q.push(1);
    int w,i=0;
    while (!q.empty())
    {
        ++i;
        viz[1]=1;
        w=q.front();
        q.pop();
        for (unsigned i=0; i<v[w].size(); i++)
        {
            if (a[v[w][i]]>a[w]+c[w][i])
            {
                a[v[w][i]]=a[w]+c[w][i];
                if (!viz[v[w][i]])
                {
                    q.push(v[w][i]);
                    viz[v[w][i]]=1;
                }
            }
        }
        viz[w]=0;
    }
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    scanf("%d%d", &n, &m);
    int x,y,z;
    for (int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        c[x].push_back(z);
        v[x].push_back(y);
    }
    memset(a, 0x3f, sizeof(a));
    a[1]=0;
    bellman_ford();
    freopen("bellmanford.out","w",stdout);
    for (int i=2; i<=n; i++)
    if (a[i]==INFI)
        printf("0 ");
    else
        printf("%d ",a[i]);
    return 0;
}