#include<stdio.h>
#include<algorithm>   
#include<vector>   
#include<queue>   
using namespace std;   
const int nmax=50010;   
const int inf=0x3f3f3f3f;
int n,m,d[nmax];   
vector<pair<int, int> >g[nmax];   
void cit()   
{   
    freopen("dijkstra.in","r",stdin);   
    scanf("%d %d",&n,&m);   
    for(;m;m--)   
    {   
        int x,y,z;   
        scanf("%d %d %d",&x,&y,&z);   
        g[x].push_back(make_pair(y,z));   
    }   
}   
void af()   
{   
    freopen("dijkstra.out","w",stdout);   
    for(int i=2;i<=n;i++)   
        printf("%d ",(d[i]<inf?d[i]:0));   
}   
void solve()   
{   
    int iq[nmax];   
    queue<int>q;   
    memset(d,inf,sizeof(d));   
    memset(iq,0,sizeof(iq));   
    d[1]=0;   
    q.push(1);   
    iq[1]=1;   
    while(!q.empty())   
    {   
        int nod=q.front();   
        q.pop();   
        iq[nod]=0;   
        for(vector<pair<int, int> >::iterator i=g[nod].begin();i!=g[nod].end();i++)   
            if(d[nod]+i->second<d[i->first])   
            {   
                d[i->first]=d[nod]+i->second;   
                if(!iq[i->first])   
                {   
                    q.push(i->first);   
                    iq[i->first]=1;   
                }   
            }   
    }   
}   
int main()   
{   
    cit();   
    solve();   
    af();   
}   
      
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define nmax 50010
#define inf 0x3f3f3f3f
int n,m,d[nmax];
vector<pair<int, int> >g[nmax];
void cit()
{
	freopen("dijkstra.in","r",stdin);
	scanf("%d %d",&n,&m);
	for(;m;m--)
	{
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		g[x].push_back(make_pair(y,z));
	}
}
void af()
{
	freopen("dijkstra.out","w",stdout);
	for(int i=2;i<=n;i++)
		printf("%d ",(d[i]<inf?d[i]:0));
}
void solve()
{
	int iq[nmax];
	queue<int>q;
	memset(d,inf,sizeof(d));
	memset(iq,0,sizeof(iq));
	d[1]=0;
	q.push(1);
	iq[1]=1;
	while(!q.empty())
	{
		int nod=q.front();
		q.pop();
		iq[nod]=0;
		for(vector<pair<int, int> >::iterator i=g[nod].begin();i!=g[nod].end();i++)
			if(d[nod]+i->second<d[i->first])
			{
				d[i->first]=d[nod]+i->second;
				if(!iq[i->first])
				{
					q.push(i->first);
					iq[i->first]=1;
				}
			}
	}
}
int main()
{
	cit();
	solve();
	af();
}