#include <fstream>
#include <vector>
#define nmax 50001
#define INF 1<<30

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m,heap[nmax],cost[nmax],poz[nmax];

vector < pair < int , int > >leg[nmax];

inline int father(int k)
{
    return k/2;
}

inline int leftson(int k)
{
    return k*2;
}

inline int rightson(int k)
{
    return k*2+1;
}

void sift(int n, int k)
{
    int son;
    do
    {
        son=0;
        if(leftson(k)<=n)
        {
            son=leftson(k);
            if(rightson(k)<=n && cost[heap[leftson(k)]]>cost[heap[rightson(k)]])
                son=rightson(k);
            if(cost[heap[son]]>=cost[heap[k]])
                son=0;
        }

        if(son)
        {
            swap(heap[k], heap[son]);
            swap(poz[heap[k]],poz[heap[son]]);
            k=son;
        }
    }
    while(son);
}

void percolate(int n, int k)
{
    int key=heap[k];
    while(k>1 && cost[key]<cost[heap[father(k)]])
    {
        heap[k]=heap[father(k)];
        poz[heap[k]]=k;
        k=father(k);
    }

    heap[k]=key;
    poz[heap[k]]=k;
}

inline void read()
{
    int i,a,b,c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        if(!c)
            c=-1;
        leg[a].push_back(make_pair(b,c));
    }

    fin.close();

    for(i=1;i<=n;i++)
    {
        heap[i]=i;
        poz[i]=i;
        cost[i]=INF;
    }
    cost[1]=0;
}

void delete_elem(int &n, int k)
{
    heap[k]=heap[n];
    poz[heap[k]]=k;
    n--;
    if(k>1 && heap[k]<heap[father(k)])
        percolate(n,k);
    else
        sift(n,k);
}

inline void solve()
{
    int z=n,i,node,a,b;
    while(z)
    {
        node=heap[1];
        delete_elem(z,1);
        for(i=0;i<leg[node].size();i++)
        {
            a=leg[node][i].first;
            b=max(leg[node][i].second,0);
            cost[a]=min(cost[a],cost[node]+b);
            if(poz[a]>1 && cost[heap[a]]<cost[heap[father(a)]])
                percolate(z,a);
            else
                sift(z,a);
        }
    }
}

inline void write()
{
    for(int i=2;i<=n;i++)
        {
            if(cost[i]==INF)
                fout<<"0 ";
            else
                fout<<cost[i]<<' ';
        }
    fout.close();
}

int main()
{
    read();
    solve();
    write();
    return 0;
}