#include <cstdio>
#include <vector>
#include <set>

using namespace std;

long n, m, i, j, heap[100100] ,poz[50100], cs[50100], nod, fiu, a, b, cc, inf, l, k;

vector <int> v[50100];
vector <int> c[50100];

set < pair<int, int> > myset;



int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    scanf("%d%d",&n,&m);
    
    l=n;
    
    for (i=1;i<=m;i++){
        scanf("%d%d%d", &a, &b, &cc);
        v[a].push_back(b);
        c[a].push_back(cc); 
        
    }
        
    inf=1000000000;
    
    for (i=0;i<=l;i++)
        cs[i]=inf;
        
    cs[1]=0;    
    k=l;
    
    myset.insert(make_pair(0, 1));
    
    while (!myset.empty()){
        
        nod = (*myset.begin()).second;                        
        myset.erase(myset.begin());        
        
        for (i=0;i<v[nod].size();i++){
            
            fiu=v[nod][i];
            
            if (cs[nod]+c[nod][i]<cs[fiu]) {
                cs[fiu]=cs[nod]+c[nod][i];
                myset.insert(make_pair(cs[fiu], fiu));
            }
//            fprintf(stderr, "%d %d %d\n", nod, fiu, cs[fiu]);            
        }
        k--;
    }        
       
    for (i=2; i<=n; i++)
        if (cs[i]==inf)
            printf("0\n");
        else
            printf("%d\n",cs[i]);
        
    return 0;
}